This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |