Submission #1191902

#TimeUsernameProblemLanguageResultExecution timeMemory
1191902prideliqueeeWatching (JOI13_watching)C++20
0 / 100
5 ms328 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define f first #define s second int a[3010]; int mn[12000]; struct st { int ex,one,two; bool operator <(const st&o) const { if(ex+one+two==o.ex+o.one+o.two) return two>o.two; return ex+one+two<o.ex+o.one+o.two; } }; void build(int l,int r,int i) { if(l==r) { mn[i]=a[l]; return; } int mid=(l+r)/2; build(l,mid,i*2); build(mid+1,r,i*2+1); mn[i]=min(mn[i*2],mn[i*2+1]); } int query(int l,int r,int i,int val) { if(l==r) return l; int mid=(l+r)/2; if(mn[i*2+1]<=val) return query(mid+1,r,i*2+1,val); else return query(l,mid,i*2,val); } signed main() { int n,p,q; cin>>n>>p>>q; for(int i=1;i<=n;i++) cin>>a[i]; a[0]=0; sort(a+1,a+n+1); build(0,n,1); int l=1,r=1e9; while(l<r) { int mid=(l+r)/2; st dp[n+1]; for(int i=0;i<=n;i++) dp[i]={0,0,0}; for(int i=1;i<=n;i++) { int index1=query(0,n,1,max((int)0,a[i]-mid)); int index2=query(0,n,1,max((int)0,a[i]-mid*2)); st p1=dp[index1],p2=dp[index2]; /*if(p1.ex==1) { p1.ex=0; p1.two+=2; } else p1.ex++;*/ p1.one++; p2.two+=2; if(p1<p2) dp[i]=p1; else dp[i]=p2; /*cout<<a[i]-mid<<" "<<a[i]-mid*2<<endl; cout<<index1<<' '<<index2<<endl; cout<<p1.ex<<" "<<p1.one<<" "<<p1.two<<'\n'; cout<<p2.ex<<" "<<p2.one<<" "<<p2.two<<'\n'; cout<<dp[i].ex<<" "<<dp[i].one<<" "<<dp[i].two<<'\n'; cout<<endl;*/ } int ex=dp[n].ex,one=dp[n].one,two=dp[n].two; int pp=p,qq=q; two/=2; if(two<=qq) { qq-=two; two=0; } else { two-=qq; qq=0; two*=2; } if(two+one+ex<=qq+pp) r=mid; else l=mid+1; } cout<<l; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...