Submission #950736

#	Time	Username	Problem	Language	Result	Execution time	Memory
950736		WonderfulWhale	Candies (JOI18_candies)	C++17	0 / 100	19 ms	53592 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, 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) {
	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;
		opt = max(opt, {A[a]+B[b], a});
	}
	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;
				}
				f(0, len-1, 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:41: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, vector<auto> v) {
      |                                         ^~~~

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