#include <bits/stdc++.h>
#include <fstream>
//#define endl '\n'
#define mod 998244353
#define INF 900000000000000000
//#define cin fin
//#define cout fout
#define fi first
#define se second
using namespace std;
//ofstream fout("intel.out");
//ifstream fin("intel.in");
int main()
{
ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
long long n; cin >> n; pair<long long, long long> arr[n]; stack<pair<long long,long long>> stl, str;
long long sum = 0;
for(int i = 0; i < n; i++) {
cin >> arr[i].first >> arr[i].second;
}
for(int i = n-1; i >= 0; i--) {
sum += arr[i].first; sum -= arr[i].second;
if(arr[i].first > 0) str.push({arr[i].first,i});
}
long long ans = 0;
for(long long i = 0; i < n; i++) {
sum += arr[i].second;
sum -= arr[i].first;
if(!str.empty() && str.top().second == i) {
str.pop();
}
long long x = arr[i].first, y = arr[i].second;
arr[i].second -= min(arr[i].second,arr[i].first);
arr[i].first -= min(x,y);
while(arr[i].second > 0) {
// cout << i << ' ' << sum << "sum" << endl;
// cout << arr[i].second << 'k' << endl;
if(sum > 0) {
if((!stl.empty() && !str.empty() && abs(str.top().second-i) < abs(stl.top().second-i)) || stl.empty()) {
// cout << 'a' << ' ' << str.top().second << endl;
if(sum >= str.top().first) {
if(arr[i].second >= str.top().first) {
arr[i].second -= str.top().first;
ans += abs(i-str.top().second)*str.top().first;
sum -= str.top().first;
arr[str.top().second].first = 0;
str.pop();
}
else {
str.top().first -= arr[i].second;
ans += abs(i-str.top().second)*arr[i].second;
sum -= arr[i].second;
arr[str.top().second].first = str.top().first;
arr[i].second = 0;
}
}
else {
if(arr[i].second >= sum) {
arr[i].second -= sum;
ans += abs(i-str.top().second)*sum;
str.top().first -= sum;
arr[str.top().second].first = str.top().first;
sum = 0;
}
else {
str.top().first -= arr[i].second;
ans += abs(i-str.top().second)*arr[i].second;
sum -= arr[i].second;
arr[str.top().second].first = str.top().first;
arr[i].second = 0;
}
}
}
else if((!stl.empty() && !str.empty() && abs(str.top().second-i) >= abs(stl.top().second-i)) || str.empty()) {
// cout << 'b' << ' ' << stl.top().second << endl;
if(arr[i].second >= stl.top().first) {
arr[i].second -= stl.top().first;
ans += abs(i-stl.top().second)*stl.top().first;
stl.pop();
}
else {
stl.top().first -= arr[i].second;
ans += abs(i-stl.top().second)*arr[i].second;
arr[i].second = 0;
}
}
}
else {
// cout << 'c' << endl;
if(arr[i].second >= stl.top().first) {
arr[i].second -= stl.top().first;
ans += abs(i-stl.top().second)*stl.top().first;
stl.pop();
}
else {
stl.top().first -= arr[i].second;
ans += abs(i-stl.top().second)*arr[i].second;
arr[i].second = 0;
}
}
}
if(arr[i].first > 0) {
stl.push({arr[i].first,i});
}
}
cout << ans;
return 0;
}
/*9
3 0
2 3
0 0
0 4
0 0
1 0
6 7
0 0
2 0
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
7 ms |
2136 KB |
Output is correct |
5 |
Correct |
13 ms |
3420 KB |
Output is correct |
6 |
Correct |
37 ms |
11812 KB |
Output is correct |
7 |
Correct |
75 ms |
23344 KB |
Output is correct |
8 |
Correct |
60 ms |
17236 KB |
Output is correct |
9 |
Correct |
60 ms |
16464 KB |
Output is correct |
10 |
Correct |
46 ms |
14176 KB |
Output is correct |
11 |
Correct |
45 ms |
14164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
7 ms |
2136 KB |
Output is correct |
5 |
Correct |
13 ms |
3420 KB |
Output is correct |
6 |
Correct |
37 ms |
11812 KB |
Output is correct |
7 |
Correct |
75 ms |
23344 KB |
Output is correct |
8 |
Correct |
60 ms |
17236 KB |
Output is correct |
9 |
Correct |
60 ms |
16464 KB |
Output is correct |
10 |
Correct |
46 ms |
14176 KB |
Output is correct |
11 |
Correct |
45 ms |
14164 KB |
Output is correct |
12 |
Incorrect |
20 ms |
5968 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
344 KB |
Output is correct |
5 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |