Submission #1024060

#TimeUsernameProblemLanguageResultExecution timeMemory
1024060lucriSails (IOI07_sails)C++17
80 / 100
1031 ms2640 KiB
#include <iostream> #include <algorithm> using namespace std; unsigned int n,hmax,cost,length; unsigned long long ans; unsigned int lss,ls,h,w; pair<unsigned int,unsigned int>v[100010],ss[100010],s[100010]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(unsigned int i=1;i<=n;++i) cin>>v[i].first>>v[i].second; sort(v+1,v+n+1); for(unsigned 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...