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;
#define int long long
const int NM = 5e5;
int n, a[NM+5], b[NM+5], c[NM+5], d[NM+5], cur = 0;
priority_queue <int> pq;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i] >> b[i];
c[i] = c[i-1]+a[i];
d[i] = d[i-1]+b[i];
}
pq.push(0);
for (int i = 1; i < n; i++){
if (c[i]-d[i] >= pq.top()){
pq.push(c[i]-d[i]);
continue;
}
cur += pq.top()-(c[i]-d[i]);
pq.pop();
if (c[i]-d[i] > 0){
pq.push(c[i]-d[i]);
pq.push(c[i]-d[i]);
}
if (pq.empty()) pq.push(0);
}
int lst = pq.top(), slope = 0;
pq.pop();
while (lst > c[n]-d[n]){
cur += slope*(lst-pq.top());
lst = pq.top();
pq.pop();
slope++;
}
cout << cur;
return 0;
}
# | 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... |