Submission #64457

#TimeUsernameProblemLanguageResultExecution timeMemory
64457TadijaSebezHomecoming (BOI18_homecoming)C++11
100 / 100
312 ms135064 KiB
#include <stdio.h> #define ll long long const int N=2000050; const int M=2*N; const ll inf=9e18; ll max(ll a, ll b){ return a>b?a:b;} ll sum[M],a[N],dp[N][2],b[M]; ll Get(int l, int r){ return sum[r]-sum[l-1];} ll solve(int n, int k, int *A, int *B) { int i,j; ll sol=0; for(i=1;i<=n;i++) a[i]=A[i-1],b[i]=-B[i-1]; for(i=n+1;i<=n*2;i++) b[i]=b[i-n]; for(i=1;i<=2*n;i++) sum[i]=sum[i-1]+b[i]; dp[1][0]=0; dp[1][1]=-inf; for(i=2;i<=n;i++) { dp[i][0]=max(dp[i-1][0],dp[i-1][1]); dp[i][1]=max(dp[i-1][0]+Get(i,i+k-1)+a[i],dp[i-1][1]+a[i]+b[i+k-1]); } sol=max(sol,max(dp[n][0],dp[n][1])); dp[1][0]=-inf; dp[1][1]=a[1]+Get(1,k); for(i=2;i<=n;i++) { dp[i][0]=max(dp[i-1][0],dp[i-1][1]); if(i+k-1<=n) dp[i][1]=max(dp[i-1][0]+Get(i,i+k-1)+a[i],dp[i-1][1]+a[i]+b[i+k-1]); else dp[i][1]=max(dp[i-1][0]+Get(i,n)+a[i],dp[i-1][1]+a[i]); } sol=max(sol,max(dp[n][0],dp[n][1])); return sol; }

Compilation message (stderr)

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:11:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...