제출 #1084874

#제출 시각아이디문제언어결과실행 시간메모리
1084874guagua0407선물상자 (IOI15_boxes)C++17
20 / 100
1 ms356 KiB
#include "boxes.h" #include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int,int> #define f first #define s second #define all(x) x.begin(),x.end() #define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long delivery(int n, int k, int l, int p[]) { vector<pair<int,int>> vec; for(int i=0;i<n;i++){ if(vec.empty() or p[i]!=vec.back().f){ vec.push_back({p[i],1}); } else{ auto pp=vec.back(); vec.pop_back(); vec.push_back({pp.f,pp.s+1}); } } auto rec=vec; int pos=-1; int sz=(int)vec.size(); for(int i=0;i<sz;i++){ if(vec[i].f<(l+1)/2){ pos=i; } } ll res; { ll ans=0; int last1=0,last2=0; if(pos!=-1){ int cur=0; while(cur<=pos){ int left=k; int mx=vec[cur].f; while(cur<=pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mx=vec[cur].f; if(vec[cur].s==0) cur++; } last1=k-left; ans+=2*mx; } } if(pos<sz-1){ int cur=sz-1; while(cur>pos){ int left=k; int mn=vec[cur].f; while(cur>pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mn=vec[cur].f; if(vec[cur].s==0) cur--; } last2=k-left; ans+=2*(l-mn); } } if(last1+last2<=k){ ll tmp=ans; if(pos>=0){ tmp-=2*vec[pos].f; } if(pos<sz-1){ tmp-=2*(l-vec[pos+1].f); } tmp+=l; ans=min(ans,tmp); } res=ans; } vec=rec; if(pos>=0){ pos--; ll ans=0; int last1=0,last2=0; if(pos!=-1){ int cur=0; while(cur<=pos){ int left=k; int mx=vec[cur].f; while(cur<=pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mx=vec[cur].f; if(vec[cur].s==0) cur++; } last1=k-left; ans+=2*mx; } } if(pos<sz-1){ int cur=sz-1; while(cur>pos){ int left=k; int mn=vec[cur].f; while(cur>pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mn=vec[cur].f; if(vec[cur].s==0) cur--; } last2=k-left; ans+=2*(l-mn); } } if(last1+last2<=k){ ll tmp=ans; if(pos>=0){ tmp-=2*vec[pos].f; } if(pos<sz-1){ tmp-=2*(l-vec[pos+1].f); } tmp+=l; ans=min(ans,tmp); } res=min(res,ans); pos++; } vec=rec; if(pos<sz-1){ pos++; ll ans=0; int last1=0,last2=0; if(pos!=-1){ int cur=0; while(cur<=pos){ int left=k; int mx=vec[cur].f; while(cur<=pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mx=vec[cur].f; if(vec[cur].s==0) cur++; } last1=k-left; ans+=2*mx; } } if(pos<sz-1){ int cur=sz-1; while(cur>pos){ int left=k; int mn=vec[cur].f; while(cur>pos and left>0){ int prv=vec[cur].s; vec[cur].s=max(0,vec[cur].s-left); left-=(prv-vec[cur].s); mn=vec[cur].f; if(vec[cur].s==0) cur--; } last2=k-left; ans+=2*(l-mn); } } if(last1+last2<=k){ ll tmp=ans; if(pos>=0){ tmp-=2*vec[pos].f; } if(pos<sz-1){ tmp-=2*(l-vec[pos+1].f); } tmp+=l; ans=min(ans,tmp); } res=min(res,ans); } return res; }
#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...