# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
199934 | 2020-02-04T07:34:08 Z | SamAnd | Potatoes and fertilizers (LMIO19_bulves) | C++17 | 1000 ms | 262148 KB |
#include <bits/stdc++.h> using namespace std; const int N = 500005, M = 30004; const long long INF = 1000000009000000009; int n; int a[N], b[N]; long long sa, sb; void solv1() { long long ans = 0; int j = 1; for (int i = 1; i <= n; ++i) { while (1) { if (b[j] >= a[i]) { ans += abs(i - j) * 1LL * a[i]; b[j] -= a[i]; a[i] = 0; break; } else { ans += abs(i - j) * 1LL * b[j]; a[i] -= b[j]; b[j] = 0; ++j; } } } printf("%lld\n", ans); } long long dp[M], ndp[M]; void solv3() { vector<int> aa, bb; for (int i = 1; i <= n; ++i) { for (int j = 0; j < a[i]; ++j) bb.push_back(i); for (int j = 0; j < b[i]; ++j) aa.push_back(i); } for (int j = 1; j <= bb.size(); ++j) dp[j] = INF; for (int i = 0; i < aa.size(); ++i) { for (int j = 0; j <= bb.size(); ++j) ndp[j] = INF; for (int j = 0; j <= bb.size(); ++j) { if (j + 1 <= bb.size()) dp[j + 1] = min(dp[j + 1], dp[j]); if (j + 1 <= bb.size()) ndp[j + 1] = min(ndp[j + 1], dp[j] + abs(aa[i] - bb[j])); } for (int j = 0; j <= bb.size(); ++j) dp[j] = ndp[j]; } long long ans = INF; for (int j = 0; j <= bb.size(); ++j) ans = min(ans, dp[j]); printf("%lld\n", ans); } int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { scanf("%d%d", &a[i], &b[i]); sa += a[i]; sb += b[i]; } if (sa == sb) solv1(); else solv3(); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 6 ms | 376 KB | Output is correct |
4 | Correct | 20 ms | 760 KB | Output is correct |
5 | Correct | 28 ms | 1144 KB | Output is correct |
6 | Correct | 84 ms | 2424 KB | Output is correct |
7 | Correct | 156 ms | 4216 KB | Output is correct |
8 | Correct | 113 ms | 4216 KB | Output is correct |
9 | Correct | 131 ms | 4216 KB | Output is correct |
10 | Correct | 119 ms | 4320 KB | Output is correct |
11 | Correct | 106 ms | 4216 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 6 ms | 376 KB | Output is correct |
4 | Correct | 20 ms | 760 KB | Output is correct |
5 | Correct | 28 ms | 1144 KB | Output is correct |
6 | Correct | 84 ms | 2424 KB | Output is correct |
7 | Correct | 156 ms | 4216 KB | Output is correct |
8 | Correct | 113 ms | 4216 KB | Output is correct |
9 | Correct | 131 ms | 4216 KB | Output is correct |
10 | Correct | 119 ms | 4320 KB | Output is correct |
11 | Correct | 106 ms | 4216 KB | Output is correct |
12 | Runtime error | 575 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
13 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 376 KB | Output is correct |
4 | Correct | 385 ms | 764 KB | Output is correct |
5 | Execution timed out | 1037 ms | 1144 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 6 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 385 ms | 764 KB | Output is correct |
6 | Execution timed out | 1037 ms | 1144 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 6 ms | 376 KB | Output is correct |
4 | Correct | 5 ms | 376 KB | Output is correct |
5 | Correct | 385 ms | 764 KB | Output is correct |
6 | Execution timed out | 1037 ms | 1144 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |