#include <cstdio> #include <algorithm> int n = 0; int m = 0; int A[500000]; unsigned long long int field[500000]; unsigned long long int dayOfLastCrop[500000]; struct greater { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < 500000; ++i) dayOfLastCrop[i] = 0; for (int i = 0; i < n; ++i) { scanf("%d", A+i); } std::sort(A, A+n, greater()); for (int i = 0; i < m; ++i) { unsigned long long int d = 0; unsigned long long int b = 0; scanf("%llu%llu", &d, &b); unsigned long long int grown = 0; unsigned long long int sum = 0; for (int j = 0; j < n; ++j) { grown = (d - dayOfLastCrop[j]) * A[j]; field[j] += grown; dayOfLastCrop[j] = d; if (field[j] > b) { sum += (field[j] - b); field[j] = b; } else break; } printf("%llu\n", sum); } return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | #include <cstdio> #include <algorithm> int n = 0; int m = 0; int A[500000]; unsigned long long int field[500000]; unsigned long long int dayOfLastCrop[500000]; struct greater { template<class T> bool operator()(T const &a, T const &b) const { return a > b; } }; int main() { scanf("%d%d", &n, &m); for (int i = 0; i < 500000; ++i) dayOfLastCrop[i] = 0; for (int i = 0; i < n; ++i) { scanf("%d", A+i); } std::sort(A, A+n, greater()); for (int i = 0; i < m; ++i) { unsigned long long int d = 0; unsigned long long int b = 0; scanf("%llu%llu", &d, &b); unsigned long long int grown = 0; unsigned long long int sum = 0; for (int j = 0; j < n; ++j) { grown = (d - dayOfLastCrop[j]) * A[j]; field[j] += grown; dayOfLastCrop[j] = d; if (field[j] > b) { sum += (field[j] - b); field[j] = b; } else break; } printf("%llu\n", sum); } return 0; } |