oj.uz

Submission #866601

# Submission time Handle Problem Language Result Execution time Memory
866601 2023-10-26T13:29:58 Z Rifal Potatoes and fertilizers (LMIO19_bulves) C++14
24 / 100
 75 ms 23344 KB 
#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.0 / 24.0

# Verdict Execution time Memory 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

Subtask #2
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #3
0 / 20.0

# Verdict Execution time Memory 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 -

Subtask #4
0 / 10.0

# Verdict Execution time Memory 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 -

Subtask #5
0 / 36.0

# Verdict Execution time Memory 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 -