#include <cstdio>
#include <vector>
#include <algorithm>
#define PB push_back
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair < int, int > pii;
const int N = 2e5 + 500;
int un[N], n;
int L[N], R[N], par[N], uk = 0, A[N];
ll pref[N][2], kol[N], sol, ans[N];
vector < pair < int, int > > v;
ll get(int l,int r,int k){
return pref[r][k] - (l ? pref[l - 1][k] : 0);
}
int pr(int x){
if(x == par[x]) return x;
return par[x] = pr(par[x]);
}
void mrg(int x,int y){
//printf("spajam %d i %d\n", x, y);
x = pr(x), y = pr(y);
if(R[y] - L[y] > R[x] - L[x])
swap(x, y);
uk -= (R[x] - L[x] + 2) / 2, sol -= kol[x];
uk -= (R[y] - L[y] + 2) / 2, sol -= kol[y];
par[y] = x;
L[x] = min(L[x], L[y]);
R[x] = max(R[x], R[y]);
if((R[x] - L[x] + 1) & 1)
kol[x] = get(L[x], R[x], L[x] & 1);
else
kol[x] = max(get(L[x], R[x], 0), get(L[x], R[x], 1));
uk += (R[x] - L[x] + 2) / 2;
sol += kol[x];
//printf("kol[ %d ] = %lld sol = %lld uk = %d\n", x, kol[x], sol, uk);
}
int main(){
scanf("%d", &n);
for(int i = 0;i < n;i++){
par[i] = i; L[i] = i; R[i] = i;
scanf("%d", A + i);
pref[i][i&1] = A[i];
v.PB({A[i], i});
}
for(int i = 1;i < n;i++)
pref[i][0] += pref[i - 1][0],
pref[i][1] += pref[i - 1][1];
sort(v.rbegin(), v.rend());
for(int j = 0;j < n;j++){
int i = v[j].Y; un[i] = 1;
uk++; kol[i] = A[i]; sol += kol[i];
if(i && un[i - 1]) mrg(i - 1, i);
if(un[i + 1]) mrg(i + 1, i);
ans[uk] = max(ans[uk], sol);
}
for(int i = 1;i <= (n + 1) / 2;i++)
printf("%lld\n", ans[i]);
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
candies.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", A + i);
~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
