Submission #61495

#	Time	Username	Problem	Language	Result	Execution time	Memory
61495		khsoo01	Homecoming (BOI18_homecoming)	C++11	100 / 100	357 ms	78920 KiB

homecoming

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

const ll N = 2000005;

ll n, k, s[2*N], dt[N], dt2[N];

ll solve (int _N, int _K, int *A, int *B) {
	n = _N;
	k = _K;
	ll R = 0;
	for(ll i=0;i<n;i++) {
		R += A[i] - B[i];
	}
	for(int i=0;i<2*n;i++) {
		s[i+1] = s[i] + B[i%n];
	}
	R = max(R, 0ll);
	ll M = 0;
	dt[0] = A[0] - s[k];
	R = max(R, dt[0]);
	M = max(M, dt[0]);
	for(ll i=1;i<n;i++) {
		dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[(i+k-1)%n]);
		R = max(R, dt[i]);
		M = max(M, dt[i]);
	}
	for(ll C=0,i=1;i<=n-k;i++) {
		C += A[n-i] - B[n-i];
		dt2[i] = max(dt2[i-1], C);
	}
	R = max(R, dt[0] + dt2[n-k]);
	M = dt[0];
	for(ll i=1;i<=n-k;i++) {
		dt[i] = max(M + A[i] - s[k+i] + s[i], dt[i-1] + A[i] - B[(i+k-1)%n]);
		R = max(R, dt[i] + dt2[n-k-i]);
		M = max(M, dt[i]);
	}
	return R;
}

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