제출 #152044

#제출 시각아이디문제언어결과실행 시간메모리
152044souhhcongHomecoming (BOI18_homecoming)C++14
0 / 100
49 ms12920 KiB
#include <iostream> //#include <homecoming.h> using namespace std; const int MAXN = 2e6+2; //int n, k; //int a[MAXN], b[MAXN]; long long dp[MAXN], pref[MAXN], ans = 0; long long get_sum(int l, int r, int N) { if (l == 0) return pref[r]; if (l <= r) return pref[r] - pref[l-1]; else return get_sum(l,N-1,N) + pref[r]; } long long int solve(int N, int K, int *A, int *B) { pref[0] = B[0]; for (int i = 1; i < N; i++) { pref[i] = pref[i-1] + B[i]; } dp[0] = max(0LL,A[0]-get_sum(0,K-1,N)); for (int i = 1; i < N; i++) { if (i >= K) dp[i] = max(dp[i], max(dp[i-1] + A[i] - B[(i+K-1)%N], dp[i-K] + A[i] - get_sum(i,(i+K-1)%N, N))); else dp[i] = max(dp[i], dp[i-1] + A[i] - B[(i+K-1)%N]); } for (int i = 0; i < N; i++) ans = max(ans,dp[i]); //cout << dp[0] << ' ' << dp[1] << ' ' << dp[2] << endl; return ans; } /* int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; cout << solve(n,k,a,b); } */ /* 3 2 40 80 100 140 0 20 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...