제출 #881035

#제출 시각아이디문제언어결과실행 시간메모리
881035winter0101휴가 (IOI14_holiday)C++14
47 / 100
357 ms18108 KiB
#include<bits/stdc++.h> #include "holiday.h" using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) const int maxn=1e5+9; struct IT{ vector<int>cnt; vector<long long>st; void resz(int n){ cnt.resize(4*n+9); st.resize(4*n+9); } void update(int n,int u,int v1,long long v2){ int id=1,l=1,r=n; while (true){ st[id]+=v2; cnt[id]+=v1; if (l==r)return; int mid=(l+r)/2; if (mid>=u){ id=id*2; r=mid; } else { id=id*2+1; l=mid+1; } } } long long walk(int n,int val){ int id=1,l=1,r=n; if (cnt[1]<=val)return st[id]; long long ans=0; while (true){ if (l==r){ if (cnt[id]>val)break; ans+=st[id]; break; } int mid=(l+r)/2; if (cnt[id*2]<val){ ans+=st[id*2]; val-=cnt[id*2]; id=id*2+1; l=mid+1; } else { id=id*2; r=mid; } } return ans; } }; long long a[maxn]; int id[maxn],revid[maxn]; int best[maxn*3]; long long dp[maxn*3]; IT st; int n,start,d; void dnc(int l,int r,int optl,int optr){ if (optl>optr||l>r)return; if (optl==optr){ for1(i,l,r){ best[i]=optl; dp[i]=st.walk(n,i-(optl-start)); } return; } int mid=(l+r)/2; for2(i,optr,optl){ long long nval=st.walk(n,mid-(i-start)); if (nval>=dp[mid]){ best[mid]=i; dp[mid]=nval; } st.update(n,revid[i],-1,-a[i]); } for1(i,optl,best[mid]){ st.update(n,revid[i],1,a[i]); } dnc(l,mid-1,optl,best[mid]); for1(i,best[mid]+1,optr){ st.update(n,revid[i],1,a[i]); } dnc(mid+1,r,best[mid],optr); } long long f[maxn*3],g[maxn*3]; int optf[maxn*3],optg[maxn*3]; void reset(){ for1(i,1,d){ best[i]=dp[i]=0; } for1(i,1,4*n)st.st[i]=st.cnt[i]=0; for1(i,1,n){ id[i]=i; } sort(id+1,id+1+n,[](int i,int j){ return a[i]>a[j]; }); for1(i,1,n)revid[id[i]]=i; for1(i,start,n){ st.update(n,revid[i],1,a[i]); } } long long solve(){ st.resz(n); reset(); dnc(1,d,start,n); for1(i,1,d){ f[i]=dp[i]; optf[i]=best[i]; } reverse(a+1,a+1+n); start=n+1-start; reset(); st.update(n,revid[start],-1,-a[start]); dnc(1,d,start+1,n); for1(i,1,d){ g[i]=dp[i]; optg[i]=n+1-best[i]; } start=n+1-start; long long ans=0; for1(i,1,d){ ans=max({ans,f[i],g[i]}); int use=d-i-(optf[i]-start); if (use>=0){ ans=max(ans,f[i]+g[use]); } use=d-i-(start-optg[i]); if (use>=0){ ans=max(ans,g[i]+f[use]); } } return ans; } long long findMaxAttraction(int N,int START,int D,int att[]){ n=N,start=START+1,d=D; for1(i,1,n){ a[i]=att[i-1]; } return solve(); } /*signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); cin>>n>>start>>d; start++; for1(i,1,n){ cin>>a[i]; } cout<<solve(); }*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...