Submission #1011445

#TimeUsernameProblemLanguageResultExecution timeMemory
1011445User0069Holiday (IOI14_holiday)C++17
0 / 100
33 ms65536 KiB
#include<bits/stdc++.h> #include<holiday.h> #define taskname "" #define el '\n' #define fi first #define sc second #define pii pair<int, int> #define all(v) v.begin(), v.end() #define int ll using namespace std; using ll=long long; using ull=unsigned long long; using ld=long double; #define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); using namespace std; const int maxn=1e6+3; const int mod=1e9+7; const int INF=1e9+1; int n,m,k,x,y,a[maxn],cur,S,opt[maxn],dp[maxn][3][2]; vector<int> v; struct node { vector<int> a; vector<int> pfs; int l,r; }ST[maxn*30]; void cons(int id,vector<int> v,int lval,int rval) { if(v.size()==0) return; int mid=(lval+rval)/2; vector<int> s[2]; ST[id].a.push_back(0); ST[id].pfs.push_back(0); for(int i:v) { int cc=ST[id].a.back()+(a[i]>mid); ST[id].a.push_back(cc); s[a[i]>mid].push_back(i); cc=ST[id].pfs.back()+(a[i]>mid)*a[i]; ST[id].pfs.push_back(cc); } v.clear(); if(rval==lval) return; if(s[0].size()) cons(ST[id].l=++cur,s[0],lval,mid); if(s[1].size()) cons(ST[id].r=++cur,s[1],mid+1,rval); } int get(int id,int k,int l,int r,int lval,int rval) { if(id==0||ST[id].a.size()<=1||k<=0) return 0; if(lval==rval) { return min(k,(int)ST[id].a.size())*lval; } int mid=(lval+rval)/2; int s1=ST[id].a[l-1]; int s2=ST[id].a[r]; if(s2-s1>k) { return get(ST[id].r,k,s1+1,s2,mid+1,rval); } else { int cnt=ST[id].pfs[r]-ST[id].pfs[l-1]; return cnt+get(ST[id].l,k-(s2-s1),l-s1,r-s2,lval,mid); } } void dnc(int l,int r,int optl,int optr,int rev,int jump) { if(l>r) return; int mid=(l+r)/2; opt[mid]=optl,dp[mid][jump][rev]=0; for(int i=optl;i<=optr;i++) { if(!rev) { int dd=i-S; int cc=get(1,mid-dd*jump,S+1,i,1,1e9); if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i; } if(rev) { int dd=S-i; int cc=get(1,mid-dd*jump,i,S-1,1,1e9); if(cc>=dp[mid][jump][rev]) dp[mid][jump][rev]=cc,opt[mid]=i; } } if(l==r) return; if(!rev) { dnc(l,mid-1,optl,opt[mid],rev,jump); dnc(mid+1,r,opt[mid],optr,rev,jump); } if(rev) { dnc(l,mid-1,opt[mid],optr,rev,jump); dnc(mid+1,r,optl,opt[mid],rev,jump); } } long long findMaxAttraction(int32_t n,int32_t start,int32_t d,int32_t b[]) { for(int i=1;i<=n;i++) v.push_back(i); for(int i=0;i<n;i++) a[i+1]=b[i]; cons(1,v,1,1e9); S=start; dnc(1,d,1,S-1,1,1); dnc(1,d,1,S-1,1,2); dnc(1,d,S+1,n,0,1); dnc(1,d,S+1,n,0,2); int ans=0; for(int i=0;i<=d;i++) { ans=max(dp[i][1][0]+dp[d-i][2][1],ans); ans=max(dp[i][1][1]+dp[d-i][2][0],ans); if(i<d) { ans=max(ans,dp[i][1][0]+dp[d-i-1][2][1]+a[S]); ans=max(ans,dp[i][1][1]+dp[d-i-1][2][0]+a[S]); } } return ans; } //signed main() //{ // if (fopen(taskname".INP","r")) // { // freopen(taskname".INP","r",stdin); // freopen(taskname".OUT","w",stdout); // } // Faster // int a[]={10,2,20,30,1}; // cout<<findMaxAttraction(5,2,7,a); //}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...