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 ll long long int
#define sz size
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
ll res = 0;
priority_queue<ll, vector<ll>, greater<ll>> vals;
vals.push(0);
ll a,b;
ll r = 0;
for (int i = 0; i < n; i++){
cin >> a >> b;
a = a-b;
r += a;
res += abs(r);
// cout << r << " - ";
if (r >= 0) vals.push(-1*r);
if (vals.sz() > 1 && vals.top() < -1*r){
// cout <<vals.top();
vals.pop();
if(r>=0)vals.push(-1*r);
}
// cout << '\n';
}
// cout << res << "\n";
while (vals.sz()>0){ res -= (r-max((ll)0,(r+vals.top()))); vals.pop();}
//cout << "\n";
cout << res << '\n';
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... |