/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;
int n;
ll a[N], T[N], lazy[N], A[N];
void build(int x){
for(int i =0; i <= 4*x; ++i) T[i] = lazy[i] = 0;
}
void push(int k){
T[k<<1] += lazy[k];
T[k<<1|1] += lazy[k];
lazy[k<<1] += lazy[k];
lazy[k<<1|1] += lazy[k];
lazy[k] = 0;
}
void upd(int l, int r, int ql, int qr, int k, ll val){
if(ql>r||l>qr) return;
if(ql <= l && r <= qr){
lazy[k] += val;
T[k] += val;
return;
}
push(k);
int m = l+r>>1;
upd(l, m, ql, qr, k<<1, val);
upd(m+1, r, ql, qr, k<<1|1, val);
T[k] = max(T[k<<1], T[k<<1|1]);
// cout << l << ' ' << r << ' ' << T[k] << '\n';
}
void upd2(int l, int r, int ql, int qr, int k, ll val){
if(ql>r || l>qr) return;
if(ql <= l && r <= qr){
T[k] = val;
return;
}
push(k);
int m = l+r>>1;
upd2(l, m, ql, qr, k<<1, val);
upd2(m+1, r, ql, qr, k<<1|1, val);
T[k] = max(T[k<<1], T[k<<1|1]);
// cout << l << ' ' << r << ' ' << T[k] << '\n';
}
ll get(int l, int r, int p, int k){
if(l > r || l > p || r < p) return 0;
if(l == r){
return T[k];
}
push(k);
int m = l+r>>1;
if(p <= m) return get(l, m, p, k<<1);
return get(m+1, r, p, k<<1|1);
}
ll dp[N];
void solve(){
cin >> n;
for(int i = 1; i <= n; ++i) cin >> a[i];
build(n);
vector<pair<ll, ll>> A;
for(int i = 1; i <= n; ++i){
A.pb({a[i], i});
dp[i] = 0;
}
dp[0] = 0;
sort(all(A), greater<pair<ll, ll>>());
vector<bool> used(n+1);
vector<int> f;
a[0] = -1;
for(int i = 0; i < n; i++){
int x = A[i].ss;
used[x] = 1;
vector<vector<int>> v;
for(int j = 1; j <= n; ++j){
if(j == 1 && used[j]) v.pb({a[1]});
else{
if(used[j] && used[j-1]) v.back().pb(a[j]);
else if(used[j]) v.pb({a[j]});
}
}
ll sum = 0, co = 0;
for(auto u: v){
ll x = 0, y = 0, xc = 0, yc = 0;
for(int i = 0; i < u.size(); i += 2){
x += u[i];
++xc;
}
for(int i = 1; i < u.size(); i += 2){
y += u[i];
++yc;
}
if(u.size() % 2 == 0){
sum += max(x, y);
co += xc;
}else{
sum += x;
co += xc;
}
}
dp[co] = max(dp[co], sum);
// if(x > y) swap(x, y);
// for(int j = n; j >= 1; --j){
// if(j >= y + 2){
// dp[j] = max((dp[y - 2] - dp[y - 1]) + a[y], (dp[x - 2] - dp[x - 1]) + a[x]) + dp[j];
// }else if(j >= x + 2){
// dp[j] = (dp[x - 2] - dp[x - 1]) + a[x] + dp[j];
// }
// }
// dp[x] = dp[x - 2] + a[x];
// dp[y] = max(dp[y - 2] + a[y], dp[x - 2] - dp[x - 1] + a[x] + dp[y]);
// // ll addx = a[x] - (used[x-1] ? a[x] - a[x - 1]);
// // ll addy = a[y] - (used[y-1] ? a[y] - a[y - 1]);
// // if(a[x] >= a[y]){
// // upd(1, n, x + 2, n, 1, );
// // upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
// // }else{
// // upd(1, n, y + 2, n, 1, a[y] - a[x]);
// // upd(1, n, x + 2, n, 1, a[x]);
// // upd2(1, n, x, x, 1, get(1, n, x - 2, 1) + a[x]);
// // upd2(1, n, y, y, 1, get(1, n, y - 2, 1) + a[y]);
// // }
// cout << *max_element(dp+1, dp+1+n);
// cout << '\n';
// used[x] = used[y] = 1;
}
for(int i = 1; i <= (n+1)/2; ++i) cout << dp[i] << '\n';
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
while(tt--){
solve();
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
candies.cpp: In function 'void upd(int, int, int, int, int, long long int)':
candies.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'void upd2(int, int, int, int, int, long long int)':
candies.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'long long int get(int, int, int, int)':
candies.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int m = l+r>>1;
| ~^~
candies.cpp: In function 'void solve()':
candies.cpp:85:38: warning: narrowing conversion of 'a[1]' from 'long long int' to 'int' [-Wnarrowing]
85 | if(j == 1 && used[j]) v.pb({a[1]});
| ~~~^
candies.cpp:85:38: warning: narrowing conversion of 'a[1]' from 'long long int' to 'int' [-Wnarrowing]
candies.cpp:88:35: warning: narrowing conversion of 'a[j]' from 'long long int' to 'int' [-Wnarrowing]
88 | else if(used[j]) v.pb({a[j]});
| ~~~^
candies.cpp:88:35: warning: narrowing conversion of 'a[j]' from 'long long int' to 'int' [-Wnarrowing]
candies.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 0; i < u.size(); i += 2){
| ~~^~~~~~~~~~
candies.cpp:100:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int i = 1; i < u.size(); i += 2){
| ~~^~~~~~~~~~
candies.cpp: In function 'int main()':
candies.cpp:144:15: warning: unused variable 'aa' [-Wunused-variable]
144 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
