#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});
}
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 {
ans += value2;
L = prev(blocks.end()) -> S;
R = r[L];
if(L == 1 || R == n) {
blocks.erase(prev(blocks.end()));
--i;
continue;
}
eraseBlock(L , R);
--L , ++R;
insertBlock(L , R);
}
//cerr << value1 << " " << value2 << " " << L << " " << R << endl;
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
candies.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
40 | main() {
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
10844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
