/***************************************************************************** * ZADANIE : Siano (runda 1A) * * AUTOR : Lukasz Kierat * *****************************************************************************/ #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { long long i, b, d, d1, n, m, val; vector<long long> rate(500001, 0), height(500001, 0); scanf ("%lld%lld", &n, &m); for (i = 0; i < n; ++i) scanf ("%lld", &rate[i]); sort (rate.begin(), rate.begin() + n); d1 = 0; while (m--) { scanf ("%lld%lld", &d, &b); for (i = val = 0; i < n; ++i) { height[i] += rate[i] * (d - d1); if (height[i] > b) { val += height[i] - b; height[i] = b; } } d1 = d; printf ("%lld\n", val); } return 0; } /*#include <cstdio> #include <vector> #include <algorithm> using namespace std; long long D, b1; int main() { long long i, b, d, n, m, d1, val; vector<long long> rate(500001), sum(500001); vector<long long>::iterator it; scanf ("%lld%lld", &n, &m); for (i = 0; i < n; ++i) scanf ("%lld", &rate[i]); sort (rate.begin(), rate.begin() + n); for (i = n - 2, sum[n - 1] = rate[n - 1]; i >= 0; --i) sum[i] = rate[i] + sum[i + 1]; d1 = b1 = 0; for (i = 0; i < n; ++i) printf ("%lld ", rate[i]); putchar ('\n'); for (i = 0; i < n; ++i) printf ("%lld ", sum[i]); putchar ('\n'); val = 0; while (m--) { scanf ("%lld%lld", &d, &b); D = (d); it = upper_bound (rate.begin(), rate.begin() + n, b, [](const long long &x, const long long &y) {return x < y * D;} ); printf ("upper_bound_id=%d, D=%lld, d=%lld, d1=%lld, b=%lld, b1=%lld **", it - rate.begin(), D, d, d1, b, b1); if (D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val > 0) { printf ("%lld\n", D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val); val += D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val; } else printf ("0\n"); d1 = d; b1 = b; } 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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | /***************************************************************************** * ZADANIE : Siano (runda 1A) * * AUTOR : Lukasz Kierat * *****************************************************************************/ #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main() { long long i, b, d, d1, n, m, val; vector<long long> rate(500001, 0), height(500001, 0); scanf ("%lld%lld", &n, &m); for (i = 0; i < n; ++i) scanf ("%lld", &rate[i]); sort (rate.begin(), rate.begin() + n); d1 = 0; while (m--) { scanf ("%lld%lld", &d, &b); for (i = val = 0; i < n; ++i) { height[i] += rate[i] * (d - d1); if (height[i] > b) { val += height[i] - b; height[i] = b; } } d1 = d; printf ("%lld\n", val); } return 0; } /*#include <cstdio> #include <vector> #include <algorithm> using namespace std; long long D, b1; int main() { long long i, b, d, n, m, d1, val; vector<long long> rate(500001), sum(500001); vector<long long>::iterator it; scanf ("%lld%lld", &n, &m); for (i = 0; i < n; ++i) scanf ("%lld", &rate[i]); sort (rate.begin(), rate.begin() + n); for (i = n - 2, sum[n - 1] = rate[n - 1]; i >= 0; --i) sum[i] = rate[i] + sum[i + 1]; d1 = b1 = 0; for (i = 0; i < n; ++i) printf ("%lld ", rate[i]); putchar ('\n'); for (i = 0; i < n; ++i) printf ("%lld ", sum[i]); putchar ('\n'); val = 0; while (m--) { scanf ("%lld%lld", &d, &b); D = (d); it = upper_bound (rate.begin(), rate.begin() + n, b, [](const long long &x, const long long &y) {return x < y * D;} ); printf ("upper_bound_id=%d, D=%lld, d=%lld, d1=%lld, b=%lld, b1=%lld **", it - rate.begin(), D, d, d1, b, b1); if (D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val > 0) { printf ("%lld\n", D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val); val += D * sum[it - rate.begin()] - (b)* (n - (it - rate.begin()) ) - val; } else printf ("0\n"); d1 = d; b1 = b; } return 0; }*/ |