Submission #1075546

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075546		vjudge1	Candies (JOI18_candies)	C++17	100 / 100	662 ms	43820 KiB

candies

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

#define int long long
#define viii vector <vector <vector <int> > >

const int NM = 2e5, inf = 1e18;

int n, a[NM+5];
int res[NM/2+5][2][2], tmp[NM/2+5];

void process(int l, int r, int j, int k, int nj, int nk, viii &f, viii &g){
	int cur = 0;
	tmp[0] = 0;
	for (int i = 1; i <= (r-l+2)/2; i++){
		while (cur+1 <= i){
			int val1 = f[cur][j][nj]+g[i-cur][nk][k], val2 = f[cur+1][j][nj]+g[i-cur-1][nk][k];
			if (val1 < 0) val1 = -inf;
			if (val2 < 0) val2 = -inf;
			if (val1 <= val2) cur++;
			else break;
		}
		tmp[i] = f[cur][j][nj]+g[i-cur][nk][k];
	}
}

void dnc(int l, int r){
	if (l == r){
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++){
				res[0][i][j] = 0;
				if (i&j) res[1][i][j] = a[l]; else res[1][i][j] = -inf;
			}
		return;
	}
	int mid = (l+r)/2;
	dnc(l, mid);
	vector <vector <vector <int> > > f((r-l+2)/2+1), g((r-l+2)/2+1);
	for (int i = 0; i <= (r-l+2)/2; i++){
		f[i].resize(2, vector <int>(2));
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				f[i][j][k] = (i <= (mid-l+2)/2 ? res[i][j][k] : -inf);
	}
	dnc(mid+1, r);
	for (int i = 0; i <= (r-l+2)/2; i++){
		g[i].resize(2, vector <int>(2));
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				g[i][j][k] = (i <= (r-mid+1)/2 ? res[i][j][k] : -inf);
	}
	
	for (int j = 0; j < 2; j++)
		for (int k = 0; k < 2; k++){
			process(l, r, j, k, 0, 1, f, g);
			for (int i = 0; i <= (r-l+2)/2; i++)
				res[i][j][k] = tmp[i];
			process(l, r, j, k, 1, 0, f, g);
			for (int i = 0; i <= (r-l+2)/2; i++)
				res[i][j][k] = max(res[i][j][k], tmp[i]);
			for (int i = 0; i <= (r-l+2)/2; i++)
				for (int nj = 0; nj < 2; nj++)
					for (int nk = 0; nk < 2; nk++)
						if (nj <= j && nk <= k) res[i][j][k] = max(res[i][j][k], res[i][nj][nk]);
		}
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	dnc(1, n);
	
	for (int i = 1; i <= (n+1)/2; i++)
		cout << res[i][1][1] << '\n';
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92