Submission #541552

#	Time	Username	Problem	Language	Result	Execution time	Memory
541552		mtxas	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	2 ms	340 KiB

bulves

#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
int 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(!b[i]&&a[i])
            r.push_front({i,a[i]});

    int ans=0;
    for(int i=1; i<=n; i++){
        if(b[i]==0)
            l.push_back({i,a[i]});
        else{
            while(!r.empty()){
                if(r.front().first<=i)
                    r.pop_front();
                else break;
            }
            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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 36