#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
ostream& operator<<(ostream &os, vector<auto> v) {
os << "{";
for(int i=0;i<sz(v);i++) {
os << v[i];
if(i!=sz(v)-1) os << ", ";
}
os << "}";
return os;
}
vector<int> V[1<<19][4];
int tab[200009];
const int INF = 1e18;
int dp[200009];
void f(int l, int r, int opt_l, int opt_r, vector<int> &A, vector<int> &B) {
if(l>r) return;
int m = (l+r)/2;
pii opt = {-INF, opt_l};
for(int a=opt_l;a<=opt_r;a++) {
int b = m-a;
if(b<0||b>=sz(B)) continue;
opt = max(opt, {A[a]+B[b], a});
}
dp[m] = opt.st;
f(l, m-1, opt_l, opt.nd, A, B);
f(m+1, r, opt.nd, opt_r, A, B);
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int N = 1;
while(N<n) N*=2;
// cerr << N << "\n";
for(int i=0;i<n;i++) {
cin >> tab[i];
}
for(int i=N;i<2*N;i++) {
for(int j=0;j<4;j++) {
V[i][j].resize(2);
fill(all(V[i][j]), -INF);
}
if(i-N<n) {
// cerr << "here\n";
V[i][3][1] = tab[i-N];
}
V[i][0][0] = 0;
}
for(int i=N-1;i;i--) {
for(int j=0;j<4;j++) {
V[i][j].resize(2*sz(V[2*i][j])-1);
fill(all(V[i][j]), -INF);
}
for(int j=0;j<4;j++) {
for(int k=0;k<4;k++) {
if((j&1)&&(k&2)) continue;
int type = (j&2)+(k&1);
int len = sz(V[i*2][j])*2-1;
for(int i=0;i<len;i++) {
dp[i] = INF;
}
f(0, len-1, 0, sz(V[i*2][j])-1, V[i*2][j], V[i*2+1][k]);
for(int a=0;a<len;a++) {
V[i][type][a] = max(V[i][type][a], dp[a]);
}
}
}
// cerr << "now: "<< i << ": ";
// for(int j=0;j<4;j++) {
// cerr << V[i][j] << "\n";
// }
}
for(int i=1;i<=(n+1)/2;i++) {
int ans = 0;
for(int j=0;j<4;j++) {
ans = max(ans, V[1][j][i]);
}
cout << ans << "\n";
}
}
Compilation message
candies.cpp:12:41: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
12 | ostream& operator<<(ostream &os, vector<auto> v) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
53592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
53592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
