Submission #1181855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181855		Antares	Candies (JOI18_candies)	C++20	100 / 100	232 ms	19912 KiB

candies

/**
Avem maximul la un pas. Pt a alege un nou element, Trebuie sa extindem o secventa. Tinem un set cu extinderile.
**/
#include <iostream>
#include <set>
#define dim 200000
#define ppp pair <long long,pair <int,int>>
#define cost first
#define l second.first
#define r second.second
using namespace std;
set <ppp> s;
set <ppp>::iterator it;
ppp pos[dim+1];
int n,v[dim+1];
long long ss[dim+1];
void init ()
{
    cin>>n;
    for (int i=1; i<=n; i++)
    {
        cin>>v[i];
        if (i==1)
            ss[1]=v[1];
        else
            ss[i]=ss[i-2]+v[i];
        pos[i]=make_pair (v[i],make_pair (i,i));
        s.insert (make_pair (v[i],make_pair (i,i)));
    }
}
long long get_cost (int st,int dr)
{
    return (ss[dr]-ss[st]-v[dr])-(ss[dr-1]-ss[st+1]+v[st+1]);
}
void solve ()
{
    long long sol=0;
    for (int i=1; i<=(n+1)/2; i++)
    {
        it=s.end (),it--;
        ppp elem=*it;
        sol+=elem.first;
        elem.l--;
        elem.r++;
        s.erase (it);
        if (s.find (pos[elem.l])!=s.end ())
            s.erase (s.find (pos[elem.l]));
        if (s.find (pos[elem.r])!=s.end ())
            s.erase (s.find (pos[elem.r]));
        ppp nelem=make_pair (pos[elem.l].cost+pos[elem.r].cost+get_cost (elem.l,elem.r),make_pair (pos[elem.l].l,pos[elem.r].r));
        if (nelem.l>0&&nelem.r<=n)
            s.insert (nelem);
        pos[nelem.l]=nelem,pos[nelem.r]=nelem;
        cout<<sol<<"\n";
    }
}
int main ()
{
    init ();
    solve ();
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 92 / 92