Submission #906022

#	Time	Username	Problem	Language	Result	Execution time	Memory
906022		PenguinsAreCute	Homecoming (BOI18_homecoming)	C++17	100 / 100	144 ms	106436 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"
#define int long long
using namespace std;
// val(i+1,j) = (Apre[j] - Apre[i]) - (Bpre[j+k-1] - Bpre[i]) + dp[i]
// maximise dp - Apre + Bpre.
long long solve(signed N, signed K, signed *A, signed *B) {
	int dp[N], Apre[N], Bpre[N+K], best = 0, ans = 0;
	for(int i=0;i<N;i++) Apre[i]=(i?Apre[i-1]:0)+A[i];
	for(int i=0;i<N+K;i++) Bpre[i]=(i?Bpre[i-1]:0)+B[i%N];
	for(int i=0;i<N;i++) {
		dp[i]=max(i?dp[i-1]:0,Apre[i]-Bpre[i+K-1]+best);
		best=max(best,dp[i]-Apre[i]+Bpre[i]);
		ans = max(ans, dp[i]);
	}
	best = 0;
	for(int i=0;i<N;i++) {
		dp[i]=max(i?dp[i-1]:(int)(-2.67e15),Apre[i]-Bpre[min(i+K-1,N-1LL)]+best);
		best=max(best,dp[i]-Apre[i]+Bpre[i]);
	}
	ans = max(ans, dp[N-1]);
	return ans;
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 38 / 38