Submission #950692

#	Time	Username	Problem	Language	Result	Execution time	Memory
950692		WonderfulWhale	Candies (JOI18_candies)	C++17	8 / 100	5016 ms	200168 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;

vector<int> f(vector<int> a, vector<int> b) {
	vector<int> ret(2*sz(a)-1, -INF);
	for(int i=0;i<sz(a);i++) {
		for(int j=0;j<sz(b);j++) {
			ret[i+j] = max(ret[i+j], a[i]+b[j]);
		}
	}
	// cerr << a << " + " << b << " = " << ret << "\n";
	return ret;
}

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);
				vector<int> v = f(V[i*2][j], V[i*2+1][k]); 
				for(int a=0;a<sz(v);a++) {
					V[i][type][a] = max(V[i][type][a], v[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: 8 / 8
• Subtask 2: 0 / 92