Submission #590310

#TimeUsernameProblemLanguageResultExecution timeMemory
590310mpawicka_77Potatoes and fertilizers (LMIO19_bulves)C++14
0 / 100
108 ms262144 KiB
#include <bits/stdc++.h> using namespace std; stack<pair<int,int>>S[500003]; stack<int>nad,nad2; int T[500003]; int main() { int n; cin>>n; for(int i=1; i<=n; i++) { int a,b; cin>>a>>b; T[i]=a-b; } for(int i=1; i<=n; i++) { if(T[i]>0) nad.push(i); while (T[i]<0 && !nad.empty()) { int k=nad.top(),w=min(-T[i],T[k]); T[k]-=w, T[i]+=w; if(T[k]==0) nad.pop(); S[i].push({k,w}); } } long long ans=0; for(int i=n; i>=1; i--) { if(T[i]>0) nad2.push(i); while(T[i]<0 && !nad2.empty()) { int k=nad2.top(),w=min(-T[i],T[k]); T[k]-=w, T[i]+=w, ans+=(k-i)*w;; if(T[k]==0) nad2.pop(); } while(!S[i].empty() && !nad2.empty()) { int k1=S[i].top().first,w=S[i].top().second,k=nad2.top(); if(k-i<=i-k1) { int v=min(w,T[k]); w-=v, T[k]-=v, T[k1]+=v; if(T[k]==0) nad2.pop(); S[i].pop(); ans+=(k-i)*v; if(w!=0) S[i].push({k1,w}); } else break; } } for(int i=1; i<=n; i++) { while(!S[i].empty()) { int k=S[i].top().first, w=S[i].top().second; ans+=abs(k-i)*w; S[i].pop(); } } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...