// vaziat meshki-ghermeze !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 2e3 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
ll a[N];
vector<ll> dp[2][2][N];
void Divide(int id, int L, int R){
// cerr << "S " << L << " " << R << '\n';
if(L + 1 == R){
dp[0][0][id] = {0};
dp[1][1][id] = {0, a[L]};
dp[0][1][id] = {0};
dp[1][0][id] = {0};
return ;
}
int mid = (L + R) >> 1;
Divide(id << 1, L, mid);
Divide(id << 1 | 1, mid, R);
for(int i = 0; i < 4; i++){
dp[i>>1&1][i&1][id].resize(1, 0);
dp[i>>1&1][i&1][id].resize(R - L + 1, -Inf);
}
for(int mkl = 0; mkl < 4; mkl ++){
for(int mkr = 0; mkr < 4; mkr ++){
int l = mkl >> 1 & 1, i = mkl & 1, j = mkr >> 1 & 1, r = mkr & 1;
if(i + j > 1) continue;
// cerr << l << i << j << r << '\n';
int pl = 0, pr = 0;
vector<ll> &lc = dp[l][i][id << 1];
vector<ll> &rc = dp[j][r][id << 1|1];
while((pl + 1 < lc.size()) || (pr + 1 < rc.size())){
int fl = -1;
if(pl + 1 == lc.size()){
fl = 1;
} else if(pr + 1 == rc.size()){
fl = 0;
} else {
if(lc[pl + 1] - lc[pl] >= rc[pr + 1] - rc[pr])
fl = 0;
else fl = 1;
}
if(fl) pr ++;
else pl ++;
dp[l][r][id][pl + pr] = max(dp[l][r][id][pl + pr], lc[pl] + rc[pr]);
}
}
}
// cerr << "Combed\n";
for(int i = 0; i < 4; i++){
dp[i>>1&1][i&1][id<<1].clear();
dp[i>>1&1][i&1][id<<1].shrink_to_fit();
dp[i>>1&1][i&1][id<<1|1].clear();
dp[i>>1&1][i&1][id<<1|1].shrink_to_fit();
}
if(id > 1){
for(int i = 0; i < 4; i++){
while(!dp[i>>1&1][i&1][id].empty() && dp[i>>1&1][i&1][id].back() < 0)
dp[i>>1&1][i&1][id].pop_back();
}
}
// cerr << "double\n";
return ;
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int sz = (n + 1) / 2;
Divide(1, 1, n + 1);
for(int i = 1; i <= sz; i++){
ll mx = -Inf;
for(int mk = 0; mk < 4; mk ++)
mx = max(mx, dp[mk&1][mk>>1 & 1][1][i]);
cout << mx << '\n';
}
return 0;
}
Compilation message
candies.cpp: In function 'void Divide(int, int, int)':
candies.cpp:51:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | while((pl + 1 < lc.size()) || (pr + 1 < rc.size())){
| ~~~~~~~^~~~~~~~~~~
candies.cpp:51:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | while((pl + 1 < lc.size()) || (pr + 1 < rc.size())){
| ~~~~~~~^~~~~~~~~~~
candies.cpp:53:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | if(pl + 1 == lc.size()){
| ~~~~~~~^~~~~~~~~~~~
candies.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | } else if(pr + 1 == rc.size()){
| ~~~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
