Submission #1024057

#TimeUsernameProblemLanguageResultExecution timeMemory
1024057lucriSails (IOI07_sails)C++11
80 / 100
1075 ms2640 KiB
#include <iostream> #include <algorithm> using namespace std; int n,hmax,cost,length; long long ans; int lss,ls,h,w; pair<int,int>v[100010],ss[100010],s[100010]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;++i) cin>>v[i].first>>v[i].second; sort(v+1,v+n+1); for(int i=1;i<=n;++i) { h=v[i].first; w=v[i].second; if(h>hmax) { cost=0; length=h-hmax; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; hmax=h; } while(w) { if(w>=s[ls].second) { ss[++lss]={s[ls].first+1,s[ls].second}; ans+=1LL*s[ls].first*s[ls].second; w-=s[ls].second; --ls; } else { ans+=1LL*w*s[ls].first; ss[++lss]={s[ls].first,s[ls].second-w}; ss[++lss]={s[ls].first+1,w}; w=0; --ls; } } cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; if(lss) { cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; if(lss) { cost=ss[lss].first; length=ss[lss].second; if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; --lss; while(lss) { s[++ls]={ss[lss].first,ss[lss].second}; --lss; } } } } 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...
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...