/* 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);
a[0] = -1;
for(int i = 0; i + 1 < n; i += 2){
int x = A[i].ss;
int y = A[i+1].ss;
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;
}
if(n % 2){
ll x = 0, y = 0;
for(int i = 1; i <= n; i += 2) x += a[i];
cout << x;
}
}
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:108:15: warning: unused variable 'y' [-Wunused-variable]
108 | ll x = 0, y = 0;
| ^
candies.cpp: In function 'int main()':
candies.cpp:117:15: warning: unused variable 'aa' [-Wunused-variable]
117 | int tt = 1, aa;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
8540 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
