Submission #80448

#TimeUsernameProblemLanguageResultExecution timeMemory
80448igziHomecoming (BOI18_homecoming)C++17
62 / 100
1064 ms141864 KiB
#include <bits/stdc++.h> #include "homecoming.h" #define maxN 2000005 using namespace std; int n,k,i,a[maxN],b[maxN]; long long dp[maxN],sb[maxN],tmp[maxN],p[maxN],q[maxN]; long long dp0(int n,int k,long long a[],long long b[]){ long long i,ans=0; deque <long long> dq; sb[n-1]=b[n-1]; for(i=n-2;i>=0;i--) sb[i]=sb[i+1]+b[i]; dp[n-1]=a[n-1]-b[n-1]; tmp[n-1]=max((long long) 0,dp[n-1]); ans=tmp[n-1]; dq.push_back(n-1); for(i=n-2;i>=0;i--){ long long x=dq.front(); dp[i]=a[i]+dp[x]-sb[i]+sb[x]; if(i+k<n) dp[i]=max(dp[i],tmp[i+k]+a[i]-sb[i]+sb[i+k]); ans=max(ans,dp[i]); tmp[i]=ans; if(dq.front()==i+k) dq.pop_front(); while(dq.size() && dp[dq.back()]+sb[dq.back()]<=dp[i]+sb[i]){ dq.pop_back(); } dq.push_back(i); } return ans; } long long solve(int n,int k,int a[],int c[]){ long long ans=0,s; int i,j; for(i=0;i<n;i++) b[i]=c[i]; for(j=0;j<k;j++){ s=0; for(i=0;i<n;i++){ p[i]=a[(i+j)%n]; if(i>=k) q[i]=b[(i+j)%n]; else q[i]=0; if(i<k) s+=b[(i+j)%n]; } ans=max(ans,dp0(n,k,p,q)-s); } for(i=k;i<n;i++){ p[i-k]=a[i]; q[i-k]=b[i]; } for(i=n-k;i<n;i++){ p[i]=0; q[i]=b[(i+k)%n]; } ans=max(ans,dp0(n,k,p,q)); return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...