# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
199936 | 2020-02-04T07:36:14 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) { memset(ndp, INF, sizeof ndp); for (int j = 0; j < bb.size(); ++j) { dp[j + 1] = min(dp[j + 1], dp[j]); ndp[j + 1] = min(ndp[j + 1], dp[j] + abs(aa[i] - bb[j])); } memcpy(dp, ndp, sizeof ndp); } 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
# | 결과 | 실행 시간 | 메모리 | 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 | 19 ms | 760 KB | Output is correct |
5 | Correct | 26 ms | 1144 KB | Output is correct |
6 | Correct | 78 ms | 2296 KB | Output is correct |
7 | Correct | 153 ms | 4216 KB | Output is correct |
8 | Correct | 104 ms | 4216 KB | Output is correct |
9 | Correct | 121 ms | 4216 KB | Output is correct |
10 | Correct | 104 ms | 4216 KB | Output is correct |
11 | Correct | 102 ms | 4344 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 19 ms | 760 KB | Output is correct |
5 | Correct | 26 ms | 1144 KB | Output is correct |
6 | Correct | 78 ms | 2296 KB | Output is correct |
7 | Correct | 153 ms | 4216 KB | Output is correct |
8 | Correct | 104 ms | 4216 KB | Output is correct |
9 | Correct | 121 ms | 4216 KB | Output is correct |
10 | Correct | 104 ms | 4216 KB | Output is correct |
11 | Correct | 102 ms | 4344 KB | Output is correct |
12 | Runtime error | 549 ms | 262148 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
13 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 376 KB | Output is correct |
2 | Correct | 5 ms | 376 KB | Output is correct |
3 | Correct | 5 ms | 760 KB | Output is correct |
4 | Correct | 371 ms | 1144 KB | Output is correct |
5 | Execution timed out | 1096 ms | 1144 KB | Time limit exceeded |
6 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 760 KB | Output is correct |
5 | Correct | 371 ms | 1144 KB | Output is correct |
6 | Execution timed out | 1096 ms | 1144 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | 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 | 760 KB | Output is correct |
5 | Correct | 371 ms | 1144 KB | Output is correct |
6 | Execution timed out | 1096 ms | 1144 KB | Time limit exceeded |
7 | Halted | 0 ms | 0 KB | - |