Submission #765023

#	Time	Username	Problem	Language	Result	Execution time	Memory
765023		minhcool	Candies (JOI18_candies)	C++17	100 / 100	232 ms	19528 KiB

candies

#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 3e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

int n, a[N];

vector<vector<int>> cal(int l, int r){// from left to right: (0,0), (0,1), (1,0), (1,1)
	if(l == r){
		vector<vector<int>> v;
		v.pb({0, 0});
		v.pb({0, 0});
		v.pb({0, 0});
		v.pb({0, a[l]});
		return v;
	}
	int mid = (l + r) >> 1;
	vector<vector<int>> cal1 = cal(l, mid), cal2 = cal(mid + 1, r);
	vector<vector<int>> ans;
	for(int i = 0; i <= 3; i++){
		vector<int> temp;
		temp.resize(r - l + 2);
		ans.pb(temp);
	}
	//int want = (l + r + 1) >> 1;
	for(int le = 0; le < 2; le++){
		for(int ri = 0; ri < 2; ri++){
			for(int mile = 0; mile < 2; mile++){
				for(int miri = 0; miri < 2; miri++){
					if(mile & miri) continue;
					int cur_opt = 0;
					int temp1 = (mid - l + 1 - (1 - le) - (1 - mile) + 1) / 2, temp2 = (r - mid - (1 - ri) - (1 - miri) + 1) / 2;  
				//	cout << temp1 << " " << temp2 << "\n";
					for(int tol = 0; tol <= temp1 + temp2; tol++){
						while(tol - cur_opt > temp2) cur_opt++;
						while(cur_opt < min(temp1, tol)){
				//			cout << cur_opt << "\n";
							int val1 = cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt];
							int val2 = cal1[(le << 1) | mile][cur_opt + 1] + cal2[(miri << 1) | ri][tol - cur_opt - 1];
						//	cout << val1 << " " << val2 << "\n";
							if(val1 < val2) cur_opt++;
							else break;
						}
					//	cout << le << " " << ri << " " << mile << " " << miri << " " << tol << " " << cur_opt << " " << cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt] << "\n";
						ans[(le << 1) | ri][tol] = max(ans[(le << 1) | ri][tol], cal1[(le << 1) | mile][cur_opt] + cal2[(miri << 1) | ri][tol - cur_opt]);
					}
				}
			}
		}
	}
	//cout << l << " " << r << "\n";
	for(int i = 0; i < 4; i++){
	//	cout << "OK ";
	//	for(int j = 0; j < ans[i].size(); j++) cout << ans[i][j] << " ";
	//	cout << "\n";
	}
	return ans;
}

#ifdef local
void process(){
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	vector<vector<int>> v = cal(1, n);
	for(int i = 1; i <= (n + 1)/2; i++) cout << max({v[0][i], v[1][i], v[2][i], v[3][i]}) << "\n"; 
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	process();
}
#endif

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