Submission #96345

#	Time	Username	Problem	Language	Result	Execution time	Memory
96345		KLPP	Homecoming (BOI18_homecoming)	C++14	31 / 100	1084 ms	56780 KiB

homecoming

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 10000000000000000
lld DP[1000000][3];
int n,k;
lld C[1000000];
lld D[1000000];
lld compute(int pos, int type){
	if(type==2 && pos+k>n)return -INF;
	if(DP[pos][type]!=-1)return DP[pos][type];
	if(type==0){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,2));
	}
	if(type==1){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1))+C[pos];
	}
	if(type==2){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1))+D[pos];
	}DP[pos][type]=max(DP[pos][type],(lld)0);
	return DP[pos][type];
}
lld solveLin(int A[], int B[]){
	
	for(int i=0;i<n;i++){
		C[i]=A[i]-B[i];
	}
	D[0]=A[0];
	for(int i=0;i<k;i++)D[0]-=B[i];
	for(int i=0;i+k<n;i++){
		D[i+1]=D[i]-A[i]+B[i]+A[i+1]-B[i+k];
	}
	for(int i=n-k+1;i<n;i++){
		D[i]=-INF;
	}
	for(int i=0;i<n;i++){
		DP[i][0]=-1;
		DP[i][1]=-1;
		DP[i][2]=-1;
	}
	DP[0][0]=0;
	DP[0][1]=C[0];
	DP[0][2]=D[0];
	/*cout<<compute(n-1,0)<<" "<<compute(n-1,1)<<" "<<compute(n-1,2)<<endl;
	for(int i=0;i<n;i++){
		for(int j=0;j<3;j++)cout<<DP[i][j]<<" ";
		cout<<endl;
	}*/
	return compute(n-1,0);
}
long long solve(int N, int K, int *A, int *B){
	n=N;
	k=K;
	lld sol=0;
	for(int i=0;i<n;i++)sol+=A[i]-B[i];
	sol=max(sol,(lld)0);
	for(int i=0;i<n;i++){
		sol=max(sol,solveLin(A,B));
		for(int j=0;j<n-1;j++){
			swap(A[j],A[j+1]);
			swap(B[j],B[j+1]);
		}//for(int j=0;j<n;j++)cout<<A[j]<<" "<<B[j]<<endl;
	}	
	return sol;
}

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