Submission #1023981

#TimeUsernameProblemLanguageResultExecution timeMemory
1023981lucriSails (IOI07_sails)C++17
80 / 100
1035 ms2644 KiB
#include <bits/stdc++.h> using namespace std; long long n,hmax; long long ans,h,w; long long v[100010],lss,ls; pair<long long,long long>s[50010],ss[50010]; static inline void adauga(long long cost,long long length) { if(ls&&cost==s[ls].first) { length+=s[ls].second; --ls; } s[++ls]={cost,length}; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; for(long long i=1;i<=n;++i) { cin>>h>>w; v[i]=h*1000000+w; } sort(v+1,v+n+1); for(long long i=1;i<=n;++i) { h=v[i]/1000000; w=v[i]%1000000; if(h>hmax) { adauga(0,h-hmax); hmax=h; } while(w) { if(w>=s[ls].second) { ss[++lss]={s[ls].first+1,s[ls].second}; ans+=s[ls].first*s[ls].second; w-=s[ls].second; --ls; } else { ans+=w*s[ls].first; ss[++lss]={s[ls].first,s[ls].second-w}; ss[++lss]={s[ls].first+1,w}; w=0; --ls; } } while(lss) { adauga(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...