Submission #611911

#TimeUsernameProblemLanguageResultExecution timeMemory
611911juggernautHomecoming (BOI18_homecoming)C++14
0 / 100
1090 ms43524 KiB
#include<bits/stdc++.h> #define fr first #define sc second using namespace std; typedef long long ll; typedef long double ld; template<class T>void umax(T &a,T b){if(a<b)a=b;} template<class T>void umin(T &a,T b){if(b<a)a=b;} #ifdef juggernaut #define printl(args...) printf(args) #else #define printl(args...) 0 #endif ll solve(int n,int k,int *A,int *B){ vector<ll>a,b,pref,dp,cost; b=cost=a=pref={0}; for(int i=0;i<2*n;i++){ a.push_back(A[i%n]); pref.push_back(pref.back()+a.back()); b.push_back(B[i%n]); cost.push_back(cost.back()+b.back()); } dp.assign(2*n+1,0); for(int i=n+1;i<=2*n;i++){ dp[i]=dp[i-1]; for(int j=n+1;j<=i;j++)if(i-j+1>=k) umax(dp[i],dp[j-1]+(pref[i+1-k]-pref[j-1])-(cost[i]-cost[j-1])); } return dp.back(); } #ifdef juggernaut int main() { int T; assert(scanf("%d", &T) == 1); for(int t = 0; t < T; t++) { int N, K; assert(scanf("%d%d", &N, &K) == 2); int *A = new int[N]; int *B = new int[N]; for(int i = 0; i < N; i++) assert(scanf("%d", &A[i]) == 1); for(int i = 0; i < N; i++) assert(scanf("%d", &B[i]) == 1); printf("%lld\n", solve(N, K, A, B)); delete[] A; delete[] B; } return 0; } #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...