Submission #1326422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326422		pasta	Candies (JOI18_candies)	C++20	0 / 100	18 ms	2036 KiB

candies

//Oh? You're Approaching Me?
 
#include <bits/stdc++.h>
//#include <fstream>
using namespace std;
//  
#define int long long

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
 
// #pragma GCC optimize("O3,unroll-loops")
#define migmig     		    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
 
const int maxn = 1e6 + 100;
const int mod = 998244353;
const int inf = 1e9 + 5;
const int LOG = 22;
#define mid		((l + r) / 2)
#define lc		(id * 2)
#define rc		(lc + 1)
//g++ main.cpp -o main && main.exe

int a[maxn];
vector<ll> dp[2][2][maxn];

void divide(int id, int l, int r) {
	if (l + 1 == r) {
		dp[0][0][id] = {0};
		dp[0][1][id] = {0};
		dp[1][0][id] = {0};
		dp[1][1][id] = {0, a[l]};
		return;
	}
	divide(lc, l, mid);
	divide(rc, mid, r);
	for(int i = 0; i < 4; i++){
		dp[i >> 1 & 1][i & 1][id].resize(1, 0);
		dp[i >> 1 & 1][i & 1][id].resize(r - l + 1, -inf);
	}
	for (int ml = 0; ml < 4; ml++) {
		for (int mr = 0; mr < 4; mr++) {
			int l1 = ml >> 1 & 1, r1 = ml & 1, l2 = mr >> 1 & 1, r2 = mr & 1;
			if (r1 + l2 > 1)
				continue;
			int pl = 0, pr = 0;
			vector<ll> &pdl = dp[l1][r1][lc];
			vector<ll> &pdr = dp[l2][r2][rc];
			while ((pl + 1 < SZ(pdl)) || (pr + 1 < SZ(pdr))) {
				if (pl + 1 == SZ(pdl))
					pr++;
				else if (pr + 1 == SZ(pdr))
					pl++;
				else {
					if (pdl[pl + 1] - pdl[pl] >= pdr[pr + 1] - pdr[pr])
						pl++;
					else
						pr++;
				}
				dp[l1][r2][id][pl + pr] = max(dp[l1][r2][id][pl + pr], pdl[pl] + pdr[pr]);
			}
		}
	}
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			dp[i][j][id].clear();
		}
	}
}

signed main() {
	migmig;
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	
	divide(1, 1, n + 1);
	for (int i = 1; i <= ((n + 1) / 2); i++) {
		ll ans = -inf;
		for (int a = 0; a < 2; a++) {
			for (int b = 0; b < 2; b++) {
				ans = max(ans, dp[a][b][1][i]);
			}
		}
		cout << ans << '\n';
	}
}

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