oj.uz

Submission #541564

# Submission time Handle Problem Language Result Execution time Memory
541564 2022-03-23T18:34:13 Z mtxas Potatoes and fertilizers (LMIO19_bulves) C++14
0 / 100
 2 ms 340 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf=1e9+7;
signed main() {
//    freopen("input.txt","r",stdin);
	int n; cin>>n;
	vector<int> a(n+1),b(n+1);
	for(int i=1; i<=n; i++){
        cin>>a[i]>>b[i];
        int m=min(a[i],b[i]);
        a[i]-=m,b[i]-=m;
	}

    deque<pair<int,int>> l,r;
    for(int i=1; i<=n; i++)
        if(a[i])
            r.push_back({i,a[i]});

    int ans=0;
    for(int i=1; i<=n; i++){
        while(!r.empty()){
                if(r.front().first<i)
                    r.pop_front();
                else break;
        }

        if(b[i]==0){
            if(r.empty()) continue;
            if(r.front().first==i){
                l.push_back(r.front());
                r.pop_front();
            }
        }
        else{
            while(b[i]){
                pair<int,int> pl=(l.empty()?make_pair(-inf,-inf):l.back());
                pair<int,int> pr=(r.empty()?make_pair(inf,-inf):r.front());
                pair<int,int> &p=(abs(pl.first-i)<abs(pr.first-i)?l.back():r.front());
                int take=min(p.second,b[i]);
                b[i]-=take;
                ans+=take*abs(p.first-i);
                if(p.second-take==0){
                    if(abs(pl.first-i)<abs(pr.first-i))
                        l.pop_back();
                    else r.pop_front();
                } else p.second-=take;
            }
        }
    }
    cout<<ans;
}

Subtask #1
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Incorrect 2 ms 340 KB Output isn't correct
4 Halted 0 ms 0 KB -