| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 204882 | egekabas | Candies (JOI18_candies) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
ll prt[200009];
ll val[200009];
ll lef[200009];
ll rig[200009];
ll evsum[200009];
ll oddsum[200009];
ll findprt(ll x){
if(prt[x] == x)
return x;
return (prt[x] = findprt(prt[x]));
}
void merge(ll x, ll y){
x = findprt(x);
y = findprt(y);
if(x == y) return;
prt[x] = y;
val[y] += val[x];
lef[y] = min(lef[x], lef[y]);
rig[y] = max(rig[x], rig[y]);
evsum[y] += evsum[x];
oddsum[y] += oddsum[x];
}
ll n;
ll a[200009];
ll ans[200009];
set<pll, greater<pll>> s;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
//freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
cin >> n;
for(ll i = 0; i < n; ++i){
cin >> a[i];
prt[i] = i;
val[i] = a[i];
lef[i] = rig[i] = i;
if(i%2)
oddsum[i] = a[i];
else
evsum[i] = a[i];
s.insert({val[i], i});
}
ll sz = 1;
ll cur = 0;
while(sz <= (n+1)/2){
pll curit = *s.begin();
s.erase(s.begin());
ll curnode = curit.ss;
if((lef[curnode] == 0 || rig[curnode] == n-1) && (rig[curnode]-lef[curnode])%2 ){
if(curit.ff <= 0)
continue;
}
else{
ans[sz] = max(ans, cur);
++sz;
}
cur += curit.ff;
//cout << lef[curnode] << ' ' << rig[curnode] << '\n';
ll befl = lef[curnode];
if(lef[curnode]-1 >= 0){
ll x = findprt(lef[curnode]-1);
assert(s.erase({val[x], x}) == 1);
merge(x, curnode);
}
curnode = findprt(curnode);
if(rig[curnode]+1 < n){
ll x = findprt(rig[curnode]+1);
assert(s.erase({val[x], x}) == 1);
merge(x, curnode);
}
curnode = findprt(curnode);
if(befl%2 == 0)
val[curnode] = oddsum[curnode]-evsum[curnode];
else
val[curnode] = evsum[curnode]-oddsum[curnode];
s.insert({val[curnode], curnode});
}
for(ll i = 1; i <= (n+1)/2; ++i)
cout << ans[i] << '\n';
}