# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
128257 | 2019-07-10T15:25:30 Z | thanos | Homecoming (BOI18_homecoming) | C++14 | 0 ms | 0 KB |
#include<homecoming.h> using namespace std; long long int C(int i,int j,int u,int *B){ int sum=0; for(int k=j; k<=j+u-1; k++){ if(j==0) break; if(k>=i){ sum-=B[k-1]; } } for(int k=i; k<=i+u-1; k++){ sum+=B[k-1]; } return sum; } long long int solve(int N,int K,int *A,int *B){ int BB[10005]; for(int i=0; i<N; i++){ BB[i]=BB[i+N]=B[i]; } long long int dp[10005]={0}; long long int mx=0; for(int i=1; i<=N; i++){ dp[i]=dp[i-1]+A[i-1]-C(i,i-1,K,BB); for(int j=i-2; j>=0; j--){ dp[i]=max(dp[i],dp[j]+A[i-1]-C(i,j,K,BB)); mx=max(mx,dp[i]); } } return mx; }