oj.uz

Submission #950765

# Submission time Handle Problem Language Result Execution time Memory
950765 2024-03-20T16:16:49 Z WonderfulWhale Candies (JOI18_candies) C++17
100 / 100
 823 ms 254048 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 53592 KB Output is correct
2 Correct 16 ms 53596 KB Output is correct
3 Correct 16 ms 53592 KB Output is correct
4 Correct 17 ms 53732 KB Output is correct
5 Correct 16 ms 53596 KB Output is correct
6 Correct 16 ms 53592 KB Output is correct
7 Correct 16 ms 53596 KB Output is correct
8 Correct 16 ms 53688 KB Output is correct
9 Correct 16 ms 53596 KB Output is correct
10 Correct 15 ms 53608 KB Output is correct
11 Correct 16 ms 53596 KB Output is correct
12 Correct 16 ms 53552 KB Output is correct
13 Correct 16 ms 53688 KB Output is correct
14 Correct 18 ms 53700 KB Output is correct
15 Correct 16 ms 53596 KB Output is correct
16 Correct 16 ms 53596 KB Output is correct
17 Correct 16 ms 53596 KB Output is correct
18 Correct 16 ms 53800 KB Output is correct
19 Correct 16 ms 53792 KB Output is correct
20 Correct 16 ms 53596 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 53592 KB Output is correct
2 Correct 16 ms 53596 KB Output is correct
3 Correct 16 ms 53592 KB Output is correct
4 Correct 17 ms 53732 KB Output is correct
5 Correct 16 ms 53596 KB Output is correct
6 Correct 16 ms 53592 KB Output is correct
7 Correct 16 ms 53596 KB Output is correct
8 Correct 16 ms 53688 KB Output is correct
9 Correct 16 ms 53596 KB Output is correct
10 Correct 15 ms 53608 KB Output is correct
11 Correct 16 ms 53596 KB Output is correct
12 Correct 16 ms 53552 KB Output is correct
13 Correct 16 ms 53688 KB Output is correct
14 Correct 18 ms 53700 KB Output is correct
15 Correct 16 ms 53596 KB Output is correct
16 Correct 16 ms 53596 KB Output is correct
17 Correct 16 ms 53596 KB Output is correct
18 Correct 16 ms 53800 KB Output is correct
19 Correct 16 ms 53792 KB Output is correct
20 Correct 16 ms 53596 KB Output is correct
21 Correct 813 ms 253592 KB Output is correct
22 Correct 805 ms 253608 KB Output is correct
23 Correct 823 ms 253584 KB Output is correct
24 Correct 730 ms 253428 KB Output is correct
25 Correct 718 ms 253548 KB Output is correct
26 Correct 738 ms 253588 KB Output is correct
27 Correct 718 ms 253536 KB Output is correct
28 Correct 777 ms 253776 KB Output is correct
29 Correct 741 ms 253572 KB Output is correct
30 Correct 738 ms 253888 KB Output is correct
31 Correct 741 ms 253776 KB Output is correct
32 Correct 740 ms 253780 KB Output is correct
33 Correct 761 ms 253360 KB Output is correct
34 Correct 751 ms 253408 KB Output is correct
35 Correct 801 ms 253440 KB Output is correct
36 Correct 768 ms 253488 KB Output is correct
37 Correct 773 ms 253688 KB Output is correct
38 Correct 784 ms 253524 KB Output is correct
39 Correct 718 ms 253556 KB Output is correct
40 Correct 737 ms 253664 KB Output is correct
41 Correct 722 ms 253644 KB Output is correct
42 Correct 715 ms 253876 KB Output is correct
43 Correct 754 ms 254048 KB Output is correct
44 Correct 718 ms 253700 KB Output is correct
45 Correct 716 ms 253576 KB Output is correct
46 Correct 715 ms 253876 KB Output is correct
47 Correct 731 ms 253612 KB Output is correct
48 Correct 750 ms 253524 KB Output is correct
49 Correct 773 ms 253632 KB Output is correct
50 Correct 750 ms 253480 KB Output is correct