This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define log(x) (63^__builtin_clzll(x))
#define endl '\n'
#define int long long
typedef long long ll;
int const M = 1e6 + 10 , lg = 23 , mod[] = {(ll)1e9 + 7 , 100000643} , block = 700;
mt19937 RNG(chrono::steady_clock::now().time_since_epoch().count());
int dx[] = {1 , -1 , 0 , 0} , dy[] = {0 , 0 , 1 , -1};
int s[M] , pref[M] , l[M] , r[M] , one[M];
set<pair<ll , ll>>blocks;
void eraseBlock(int L , int R) {
one[L] = one[R] = 0;
int value = (pref[R + 1] - (L - 3 >= 1 ? pref[L - 3] : 0)) - (pref[R] - (L - 2 >= 1 ? pref[L - 2] : 0));
blocks.erase({value , L});
}
void insertBlock(int L , int R) {
one[L] = one[R] = 1;
l[R] = L , r[L] = R;
int value = (pref[R + 1] - (L - 3 >= 1 ? pref[L - 3] : 0)) - (pref[R] - (L - 2 >= 1 ? pref[L - 2] : 0));
blocks.insert({value , L});
}
void merge(int l1 , int r1 , int l2 , int r2) {
eraseBlock(l1 , r1);
eraseBlock(l2 , r2);
insertBlock(l1 , r2);
}
main() {
ios_base::sync_with_stdio(false);cout.tie(nullptr);cin.tie(nullptr);
int n;
cin >> n;
set<pair<ll , ll>>free;
for(int i = 1 ; i <= n ; ++i) {
cin >> s[i];
pref[i] = s[i];
if(i - 2 >= 1) pref[i] += pref[i - 2];
free.insert({s[i] , i});
}
pref[n + 1] = pref[n - 1];
int ans = 0;
for(int i = 1 ; i <= (n + 1) / 2 ; ++i) {
int value1 = -1e18 , value2 = -1e18;
if(free.size()) value1 = prev(free.end()) -> F;
if(blocks.size()) value2 = prev(blocks.end()) -> F;
int L , R;
if(value1 > value2) {
ans += value1;
int index = prev(free.end()) -> S;
free.erase({s[index] , index});
insertBlock(index , index);
L = R = index;
}
else {
L = prev(blocks.end()) -> S;
R = r[L];
eraseBlock(L , R);
if(L == 1 || R == n) {
--i;
continue;
}
--L , ++R;
ans += value2;
insertBlock(L , R);
}
if(L - 1 >= 1) free.erase({s[L - 1] , L - 1});
if(R + 1 <= n) free.erase({s[R + 1] , R + 1});
if(L - 2 >= 1 && one[L - 2]) {
merge(l[L - 2] , L - 2 , L , R);
L = l[R];
}
if(R + 2 <= n && one[R + 2]) {
merge(L , R , R + 2 , r[R + 2]);
R = r[L];
}
cout << ans << endl;
}
return 0;
}
Compilation message (stderr)
candies.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
40 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |