Submission #912369

#TimeUsernameProblemLanguageResultExecution timeMemory
912369vjudge1Potatoes and fertilizers (LMIO19_bulves)C++17
54 / 100
872 ms24304 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 2e6 + 100; int n, m; long long dp[60300]; long long d[60300]; long long A, B; int a[maxn], b[maxn]; long long p[maxn]; long long rp[maxn]; int main() { cin >> n; long long cur = 0; for(int i=1; i<=n; i++) { cin >> a[i] >> b[i]; A += a[i]; B += b[i]; p[i] = p[i-1] + abs(A-B); } long long ca = 0, cb = 0; for(int i = n; i >= 1; i--) { rp[i] = rp[i+1] + abs(ca-cb); ca += a[i]; cb += b[i]; } if(A <= 30000) { for(int j = 0; j <= 2*A; j++) { dp[j] = 1e18; } dp[A] = 0; for(int i = 1; i <= n; i++) { for(int j = 0; j <= 2 * A; j++) { d[j] = dp[j] + abs(j-A); dp[j] = 1e18; } for(int j = 0; j <= 2 * A; j++) { int k = j + a[i] - b[i]; if(k >= 0 && k <= 2 * A) { dp[k] = min(dp[k], d[j]); } } for(int j = 2 * A-1; j >= 0; j--) { dp[j] = min(dp[j+1], dp[j]); } } cout << dp[A]; } else { long long ans = 1e18; for(int i = 1; i <= n; i++) { ans = min(ans, p[i-1] + rp[i]); } cout << ans << "\n"; } }

Compilation message (stderr)

bulves.cpp: In function 'int main()':
bulves.cpp:13:15: warning: unused variable 'cur' [-Wunused-variable]
   13 |     long long cur = 0;
      |               ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...