#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
struct Group
{
ll val;
pair<int,int> seg;
Group(ll a=0, int b=0, int c=0){ val=a;seg=mp(b,c);}
Group(ll a, pair<int,int> b){ val=a;seg=b;}
bool operator < (Group b) const { return val>b.val;}
};
set<Group> best;
set<pair<int,int> > ord;
set<pair<int,int> >::iterator it;
const int N=400050;
int a[N],n;
ll sum[N];
ll get(pair<int,int> p){ return sum[p.second]+(p.first>0?sum[p.first-1]:0);}
void Del(pair<int,int> p)
{
//printf("Del: (%i %i)\n",p.first,p.second);
if(p.first>=1 && p.second<=n) best.erase(Group(get(p),p));
ord.erase(p);
}
void Ins(pair<int,int> p)
{
//printf("Ins: (%i %i)\n",p.first,p.second);
if(p.first>=1 && p.second<=n) best.insert(Group(get(p),p));
if(p.first>=1 || p.second<=n) ord.insert(p);
}
int main()
{
int i;
scanf("%i",&n);
for(i=1;i<=n;i++)
{
scanf("%i",&a[i]);
sum[i]=-sum[i-1]+a[i];
ord.insert(mp(i,i));
best.insert(Group(a[i],i,i));
}
for(i=n+1;i<=n*2;i++) sum[i]=-sum[i-1];
ll sol=0;int cnt=0;
while(best.size())
{
Group tmp=*best.begin();
//best.erase(tmp);
sol+=tmp.val;
it=ord.find(tmp.seg);
pair<int,int> dl=*it;
//printf("%i %i\n",tmp.seg.first,tmp.seg.second);
tmp.seg.first--;
tmp.seg.second++;
pair<int,int> p;
if(it!=ord.begin())
{
it--;p=*it;it++;
//printf("Left: (%i %i)\n",p.first,p.second);
if(p.second==tmp.seg.first)
{
Del(p);
//best.erase(Group(get(p),p));
//ord.erase(p);
tmp.seg.first=p.first;
}
}
it++;
if(it!=ord.end())
{
p=*it;
//printf("Right: (%i %i)\n",p.first,p.second);
if(p.first==tmp.seg.second)
{
Del(p);
//best.erase(Group(get(p),p));
//ord.erase(p);
tmp.seg.second=p.second;
}
}
it--;
Del(dl);
//ord.erase(*it);
Ins(tmp.seg);
//if(tmp.seg.first>=1 || tmp.seg.second<=n)
//{
// if(tmp.seg.first>=1 && tmp.seg.second<=n) best.insert(Group(get(tmp.seg),tmp.seg));
// ord.insert(tmp.seg);
//}
cnt++;//printf("%i ",cnt);
printf("%lld\n",sol);
//if(cnt==(n+1)/2) break;
}
return 0;
}
Compilation message
candies.cpp: In function 'int main()':
candies.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&n);
~~~~~^~~~~~~~~
candies.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
752 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
632 KB |
Output is correct |
| 2 |
Correct |
5 ms |
752 KB |
Output is correct |
| 3 |
Incorrect |
4 ms |
752 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
