제출 #96349

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
96349		KLPP	Homecoming (BOI18_homecoming)	C++14	31 / 100	1076 ms	43412 KiB

homecoming

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 10000000000000000
lld DP[1000000][2];
int n,k;
lld C[1000000];
lld D[1000000];
lld compute(int pos, int type){
	if(DP[pos][type]!=-1)return DP[pos][type];
	if(type==0){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1)+D[pos-1]);
	}
	if(type==1){
		DP[pos][type]=max(compute(pos-1,0),compute(pos-1,1)+C[pos-1]);
	}
	
	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[0][0]=0;
	DP[0][1]=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<2;j++)cout<<compute(i,j)<<" ";
		cout<<endl;
	}*/
	return compute(n,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