Submission #866601

#	Time	Username	Problem	Language	Result	Execution time	Memory
866601		Rifal	Potatoes and fertilizers (LMIO19_bulves)	C++14	24 / 100	75 ms	23344 KiB

bulves

#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
*/

• Subtask 1: 24 / 24
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36