oj.uz

Submission #866585

# Submission time Handle Problem Language Result Execution time Memory
866585 2023-10-26T12:57:49 Z Rifal Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 1 ms 456 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) {

           if(sum > 0) {
          
                if((!stl.empty() && !str.empty() && abs(str.top().second-i) < abs(stl.top().second-i)) || stl.empty()) {
                    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 = str.top().first;
                        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()) {
                    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 {
                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;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 456 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 1 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -