Submission #63431

#	Time	Username	Problem	Language	Result	Execution time	Memory
63431		jangwonyoung	Homecoming (BOI18_homecoming)	C++14	100 / 100	270 ms	110276 KiB

homecoming

#include<iostream>
#include "homecoming.h"
using namespace std;
typedef long long ll;
ll pref[4000001];
ll C[4000001];
ll dp[2000001][2][2];
ll solve(int N,int K,int *A,int *B){
	pref[0]=0;
	for(int i=1; i<=2*N ;i++){
		pref[i]=pref[i-1]+B[(i-1)%N];
	}
	dp[0][0][0]=0;
	dp[0][1][1]=A[0]-pref[K];
	dp[0][1][0]=dp[0][0][1]=-1e18;
	for(int i=1; i<N ;i++){
		int j=(i+K-1);
		dp[i][0][0]=max(dp[i-1][0][0],dp[i-1][0][1]);
		dp[i][0][1]=max(dp[i-1][0][0]-pref[i+K]+pref[i],dp[i-1][0][1]-B[j%N])+A[i];
		dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]);
		dp[i][1][1]=max(dp[i-1][1][0]-pref[min(i+K,N)]+pref[i],dp[i-1][1][1]-(j>=N?0:B[j]))+A[i];
	}
	return max(max(dp[N-1][0][0],dp[N-1][0][1]),max(dp[N-1][1][0],dp[N-1][1][1]));
}

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