Submission #1104040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104040		FanOfWilliamLin	Candies (JOI18_candies)	C++14	100 / 100	75 ms	15168 KiB

candies

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second  
#define all(x) (x).begin(), (x).end()
 
const ll N = 2e5 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 350;
ll a[N], prv[N], nxt[N], del[N], ans[N];
ll n;
struct cmp{
	bool operator()(const pll &a, const pll &b){
		return a.S < b.S;
	}
};
void to_thic_cau(){ 
	cin >> n;
	priority_queue<pll, vector<pll>, cmp>q;
	for(int i = 1; i <= n;i++){
		cin >> a[i];
		prv[i] = i - 1, nxt[i] = i + 1;
		q.push({i, a[i]});
	}
	prv[n+1] = n, nxt[0] = 1, a[0] = a[n+1] = -inf;
	ll cur = (n + 1) / 2, cnt = 0, res = 0;
	while(cnt < cur){
		if(!q.size()) break;
		ll i = q.top().F, val = q.top().S; q.pop();
		if(!del[i] && i > 0 && i <= n){
			del[prv[i]] = del[nxt[i]] = 1;
			res += val;
			a[i] = a[prv[i]] + a[nxt[i]] - val;
			q.push({i, a[i]});
			nxt[i] = nxt[nxt[i]]; prv[i] = prv[prv[i]];
			nxt[prv[i]] = i;
			prv[nxt[i]] = i;
			cnt++;
		}
		ans[cnt] = max(ans[cnt], res);
	}
	for(int i = 1; i <= cur;i++) cout << ans[i] << ' ';
	cout << '\n';
}     
 
signed main()   
{  
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll tc = 1;
	//cin >> tc;
	while(tc--) to_thic_cau();
}

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