Submission #950765

#	Time	Username	Problem	Language	Result	Execution time	Memory
950765		WonderfulWhale	Candies (JOI18_candies)	C++17	100 / 100	823 ms	254048 KiB

candies

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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

ostream& operator<<(ostream &os, pair<auto, auto> x) {
	os << "{";
	os << x.st << ", " << x.nd;
	os << "}";
	return os;
}

ostream& operator<<(ostream &os, vector<auto> v) {
	os << "{";
	for(int i=0;i<sz(v);i++) {
		os << v[i];
		if(i!=sz(v)-1) os << ", ";
	}
	os << "}";
	return os;
}

vector<int> V[1<<19][4];
int tab[200009];
const int INF = 1e18;

int dp[200009];
void f(int l, int r, int opt_l, int opt_r, vector<int> &A, vector<int> &B) {
	// cerr << "f: " << l << " "<< r << " " << opt_l << " " << opt_r << "\n";
	if(l>r) return;
	int m = (l+r)/2;
	pii opt = {-INF, -opt_l};
	for(int a=opt_l;a<=opt_r;a++) {
		int b = m-a;
		if(b<0||b>=sz(B)) continue;
		// cerr << a << " " << b << " " << A[a]+B[b] << " xdxd\n";
		opt = max(opt, {A[a]+B[b], -a});
	}
	// if(m==20) cerr << opt << " xd\n";
	dp[m] = opt.st;
	f(l, m-1, opt_l, -opt.nd, A, B);
	f(m+1, r, -opt.nd, opt_r, A, B);
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	int N = 1;
	while(N<n) N*=2;
	// cerr << N << "\n";
	for(int i=0;i<n;i++) {
		cin >> tab[i];
	}
	for(int i=N;i<2*N;i++) {
		for(int j=0;j<4;j++) {
			V[i][j].resize(2);
			fill(all(V[i][j]), -INF);
		}
		if(i-N<n) {
			// cerr << "here\n";
			V[i][3][1] = tab[i-N];
		}
		V[i][0][0] = 0;
	}
	for(int i=N-1;i;i--) {
		for(int j=0;j<4;j++) {
			V[i][j].resize(2*sz(V[2*i][j])-1);
			fill(all(V[i][j]), -INF);
		}
		for(int j=0;j<4;j++) {
			for(int k=0;k<4;k++) {
				if((j&1)&&(k&2)) continue;
				int type = (j&2)+(k&1);
				int len = sz(V[i*2][j])*2-1;
				for(int i=0;i<len;i++) {
					dp[i] = -INF;
				}
				int min_a=INF, max_a=-INF, min_b=INF, max_b=-INF;
				for(int a=0;a<sz(V[i*2][j]);a++) {
					if(V[i*2][j][a]>=0) {
						min_a = min(min_a, a);
						max_a = max(max_a, a);
					}
				}
				for(int a=0;a<sz(V[i*2+1][k]);a++) {
					if(V[i*2+1][k][a]>=0) {
						min_b = min(min_b, a);
						max_b = max(max_b, a);
					}
				}

				f(min_a+min_b, max_a+max_b, 0, sz(V[i*2][j])-1, V[i*2][j], V[i*2+1][k]);
				for(int a=0;a<len;a++) {
					V[i][type][a] = max(V[i][type][a], dp[a]);
				}
			}
		}
		// cerr << "now: "<< i << ": ";
		// for(int j=0;j<4;j++) {
		// 	cerr << V[i][j] << "\n";
		// }
	}
	for(int i=1;i<=(n+1)/2;i++) {
		int ans = 0;
		for(int j=0;j<4;j++) {
			ans = max(ans, V[1][j][i]);
		}
		cout << ans << "\n";
	}
}

Compilation message (stderr)

candies.cpp:12:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                       ^~~~
candies.cpp:12:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                             ^~~~
candies.cpp:19:41: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | ostream& operator<<(ostream &os, vector<auto> v) {
      |                                         ^~~~

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