Submission #295439

#TimeUsernameProblemLanguageResultExecution timeMemory
295439BruteforcemanPotatoes and fertilizers (LMIO19_bulves)C++11
64 / 100
1089 ms15096 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 10; long long pre[maxn]; int a[maxn], b[maxn]; int main() { int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> a[i] >> b[i]; pre[i] = pre[i - 1] + a[i] - b[i]; } while(pre[n] > 0) { int cnt = 0; int best = 0, id = n; for(int i = n; i >= 1; i--) { if(pre[i] > 0) ++cnt; else --cnt; if(best < cnt) { best = cnt; id = i; } } long long minVal = pre[n]; for(int i = id; i <= n; i++) { if(pre[i] > 0) minVal = min(minVal, pre[i]); } for(int i = id; i <= n; i++) { pre[i] -= minVal; } } long long ans = 0; for(int i = 1; i <= n; i++) ans += abs(pre[i]); cout << ans << endl; }
#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...