Submission #1145290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145290		Unforgettablepl	Homecoming (BOI18_homecoming)	C++20	100 / 100	125 ms	94280 KiB

homecoming

#include "homecoming.h"
#include <bits/stdc++.h>
using namespace std;


long long int solve(int N,int K,int *A,int *B){
	vector<long long> DP(N+1),Pa(2*N+1),Pb(2*N+1);
	for(int i=1;i<=N;i++){Pa[i]=A[i-1];Pb[i]=Pb[i+N]=B[i-1];}
	for(int i=1;i<=2*N;i++){Pa[i]+=Pa[i-1];Pb[i]+=Pb[i-1];}
	auto calc = [&](){
		long long best = 0;
		for(int i=1;i<=N;i++){
			best = max(best,-Pa[i-1]+Pb[i-1]+DP[i-1]);
			DP[i]=max(DP[i-1],Pa[i]-Pb[i+K-1]+best);
		}
		return DP[N];
	};
	long long ans = calc();
	for(int i=N+1;i<=2*N;i++)Pb[i]=Pb[i-1];
	DP[0]=-3e15;
	return max(ans,calc());
}

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