Submission #1155005

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155005		alexdd	Holiday (IOI14_holiday)	C++20	7 / 100	5094 ms	7904 KiB

holiday

#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9;
int n,start,d;
int a[100005];
struct config
{
    int le,ri;
    set<pair<int,int>> luate,neluate;
    ll sum_luate;
    bool good()
    {
        if(2*(ri-start) + (start-le) + (int)luate.size() <= d)
            return 1;
        //assert(luate.empty());
        return 0;
    }
    void increase_le()
    {
        if(luate.find({a[le],le})!=luate.end())
        {
            luate.erase({a[le],le});
            sum_luate -= a[le];
        }
        else
            neluate.erase({a[le],le});
        le++;
        assert(le<=start);
        assert(ri>=start);
    }
    void decrease_le()
    {
        le--;
        baga(le);
        balance();
        assert(le<=start);
        assert(ri>=start);
    }
    void increase_ri()
    {
        ri++;
        baga(ri);
        balance();
        assert(le<=start);
        assert(ri>=start);
    }
    void baga(int x)
    {
        if(!luate.empty() && a[x] >= (*luate.begin()).first)
        {
            sum_luate -= (*luate.begin()).first;
            neluate.insert(*luate.begin());
            luate.erase(luate.begin());

            luate.insert({a[x],x});
            sum_luate += a[x];
        }
        else
            neluate.insert({a[x],x});
    }
    void balance()
    {
        while(!luate.empty() && 2*(ri-start) + (start-le) + (int)luate.size() > d)
        {
            sum_luate -= (*luate.begin()).first;
            luate.erase(luate.begin());
        }
        while(!neluate.empty() && 2*(ri-start) + (start-le) + (int)luate.size() + 1 <= d)
        {
            sum_luate += (*prev(neluate.end())).first;
            luate.insert(*prev(neluate.end()));
            neluate.erase(prev(neluate.end()));
        }
    }
    void init(int init_le, int init_ri)
    {
        le = init_le;
        ri = init_ri;
        assert(le<=start);
        assert(ri>=start);
        vector<pair<int,int>> v;
        for(int i=le;i<=ri;i++)
            v.push_back({a[i],i});
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        luate.clear();
        neluate.clear();
        sum_luate=0;
        int ramase = d - 2*(ri-start) - (start-le);
        for(int i=0;i<min((int)v.size(),ramase);i++)
        {
            sum_luate += v[i].first;
            luate.insert(v[i]);
        }
        for(int i=ramase;i<v.size();i++)
            neluate.insert(v[i]);
    }
};
ll solve()
{
    ll mxm=0;

    /*for(int le=start;le>0;le--)
    {
        config c;
        c.init(le,start);
        for(int ri=start;ri<=n;ri++)
        {
            if(c.good()) mxm = max(mxm, c.sum_luate);
            if(ri<n) c.increase_ri();
        }
    }*/

    config c;
    c.init(1,start);
    for(int ri=start;ri<=n;ri++)
    {
        if(ri!=start) c.increase_ri();
        while(c.le+1<=start)
        {
            c.init(c.le,c.ri);
            ll aux=c.sum_luate, unde=c.le, init_unde=c.le;
            int cati = min(24,start-c.le);
            for(int pas=1;pas<=cati;pas++)
            {
                c.increase_le();
                c.init(c.le,c.ri);
                ll x = c.sum_luate;
                if(x >= aux)
                {
                    aux = x;
                    unde = c.le;
                }
            }
            while(c.le > unde)
                c.decrease_le();
            c.init(c.le,c.ri);
            if(unde==init_unde)
                break;
        }
        mxm = max(mxm, c.sum_luate);
    }
    return mxm;
}
ll findMaxAttraction(int cit_n, int cit_start, int cit_d, int cit_a[])
{
    n = cit_n;
    start = cit_start + 1;
    d = cit_d;
    for(int i=0;i<n;i++)
        a[i+1] = cit_a[i];
    ll idk = solve();
    reverse(a+1,a+1+n);
    start = n - start + 1;
    idk = max(idk, solve());
    return idk;
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53