#include<bits/stdc++.h>
using namespace std;
int N, a[200009], t[200009], id[200009], lft[200009], rgt[200009], isActive[200009];
long long s[200009];
bool canTake[200009], taken[200009];
set < pair < long long, int > > S;
bool cmp (int i, int j)
{
return a[i] > a[j];
}
int tata (int x)
{
if (t[x] == x) return x;
return t[x];
}
long long extraP[200009];
void refresh (int root)
{
S.erase ({extraP[root], root});
int r = rgt[root], l = lft[root];
if (r < N && l > 1)
{
long long ld = s[r] - s[l - 2], nw = s[r + 1] - (l >= 3 ? s[l - 3] : 0);
extraP[root] = nw - ld, S.insert ({extraP[root], root});
}
}
int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
scanf ("%d", &N);
for (int i=1; i<=N; i++)
scanf ("%d", &a[i]), s[i] = a[i] + (i > 2 ? s[i - 2] : 0), id[i] = i, canTake[i] = 1, taken[i] = 0;
sort (id + 1, id + N + 1, cmp);
int pntr = 1;
long long ans = 0;
for (int K=1; K<=(N + 1) / 2; K++)
{
/* printf ("%d: ", K);
for (auto it : S)
printf ("(%lld, %d) ", it.first, it.second);*/
while (!S.empty () && isActive[S.rbegin ()->second] == 0)
{
// printf ("del (%d) ", S.rbegin ()->second);
auto it = S.end (); it --;
S.erase (it);
}
// printf ("\n");
while (!canTake[id[pntr]] && pntr <= N) pntr ++;
long long price1 = (pntr > N ? -1LL << 60 : (long long) a[id[pntr]]), price2 = (S.empty () ? -1LL << 60 : S.rbegin ()->first);
if (price1 > price2)
{
ans += price1;
int pos = id[pntr];
//printf ("add %d\n", pos);
taken[pos] = 1, canTake[pos] = canTake[pos - 1] = canTake[pos + 1] = 0;
if (pos >= 2 && t[pos - 2] > 0 && t[pos + 2] > 0)
{
int r1 = tata (t[pos - 2]), r2 = tata (t[pos + 2]);
t[r2] = t[pos] = r1, isActive[r2] = 0;
rgt[r1] = rgt[r2], refresh (r1);
}
else
if (pos >= 2 && t[pos - 2] > 0)
{
int r = tata (pos - 2);
t[pos] = r, rgt[r] = pos, refresh (r);
}
else
if (t[pos + 2] > 0)
{
int r = tata (pos + 2);
t[pos] = r, lft[r] = pos, refresh (r);
}
else t[pos] = pos, isActive[pos] = 1, lft[pos] = rgt[pos] = pos, refresh (pos);
}
else
{
ans += price2;
int root = S.rbegin ()->second;
//printf ("extend %d\n", root);
lft[root] --, rgt[root] ++;
t[lft[root]] = t[rgt[root]] = root;
canTake[lft[root] - 1] = canTake[rgt[root] + 1] = 0;
if (lft[root] - 2 >= 1 && t[lft[root] - 2] > 0)
{
int r1 = tata (lft[root] - 2);
t[r1] = root, lft[root] = lft[r1], isActive[r1] = 0;
}
if (t[rgt[root] + 2] > 0)
{
int r2 = tata (rgt[root] + 2);
t[r2] = root, rgt[root] = rgt[r2], isActive[r2] = 0;
}
refresh (root);
}
/* for (int i=1; i<=N; i++)
if (canTake[i]) printf ("1");
else printf ("0");
printf ("\n");*/
printf ("%lld\n", ans);
}
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &N);
~~~~~~^~~~~~~~~~
candies.cpp:40:89: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf ("%d", &a[i]), s[i] = a[i] + (i > 2 ? s[i - 2] : 0), id[i] = i, canTake[i] = 1, taken[i] = 0;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
