Submission #60918

#	Time	Username	Problem	Language	Result	Execution time	Memory
60918		spencercompton	Homecoming (BOI18_homecoming)	C++14	62 / 100	1068 ms	78836 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;
typedef long long ll;
ll pre[4000001];
long long int solve(int N, int K, int *A, int *B){
	ll ans = 0LL;
	for(int z = 0; z<=K; z++){
		ll here = 0LL;
		for(int i = 0; i<z; i++){
			here -= B[i];
		}
		pre[0] = 0LL;
		for(int i = 1; i<=N; i++){
			if(i<=z){
				pre[i] = 0LL;
				pre[i+N] = 0LL;
			}
			else{
				pre[i] = B[i-1];
				pre[i+N] = B[i-1];
			}
		}
		for(int i = 1; i<=2*N; i++){
			pre[i] += pre[i-1];
		}
		ll f[N];
		//choosing to buy whole thing
		ll g[N];
		//choosing to add last one

		//[i,i+K-1]
		for(int i = N-1; i>=0; i--){
			f[i] = 0;
			g[i] = 0;
			//F
			ll takeF = pre[i+K] - pre[i];
			takeF = -takeF;
			takeF += A[i];
			if(i<N-1){
				takeF += g[i+1];
			}
			f[i] = max(f[i],takeF);
			if(i<N-1){
				f[i] = max(f[i],f[i+1]);
			}

			//G

			int aft = i+K-1;
			int ind = aft;
			if(ind>=N){
				ind -= N;
			}
			//take it
			ll takeG = A[i];
			if(ind>=z){
				takeG -= B[ind];
			}
			if(i<N-1){
				takeG += g[i+1];
			}
			g[i] = max(takeG,g[i]);
			if(aft+1<N){
				g[i] = max(g[i],f[aft+1]);
			}

		}
		here += f[0];
		ans = max(ans,here);
	}
	return ans;
}

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