제출 #611915

#제출 시각아이디문제언어결과실행 시간메모리
611915juggernautHomecoming (BOI18_homecoming)C++14
13 / 100
1085 ms59920 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 solve2(int n,int k,deque<ll>A,deque<ll>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 max(dp.back(),accumulate(A.begin(),A.end(),0ll)-accumulate(B.begin(),B.end(),0ll)); } ll solve(int n,int k,int *A,int *B){ int N=n+2; ll ans=0; deque<ll>x,y; for(int i=0;i<n;i++){ x.push_back(A[i]); y.push_back(B[i]); } while(N--){ umax(ans,solve2(n,k,x,y)); x.push_back(x.front()); x.pop_front(); y.push_back(y.front()); y.pop_front(); } return ans; } #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...