Submission #1154217

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154217		alexdd	Holiday (IOI14_holiday)	C++20	24 / 100	5086 ms	6916 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[ri],ri});
    }
    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());
        sum_luate=0;
        int mnm=INF;
        for(int i=0;i<v.size();i++)
        {
            mnm = min(mnm, v[i].second);
            if(d - 2*(ri-start) - (start-mnm) < i+1)
            {
                for(int j=i;j<v.size();j++)
                    neluate.insert(v[j]);
                break;
            }
            sum_luate += v[i].first;
            luate.insert(v[i]);
        }
    }
};
ll solve()
{
    ll mxm=0;
    for(int le=1;le<=start;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();
        }
    }
    /*int poz=1;
    for(int ri=start;ri<=n;ri++)
    {
        while(poz+1<=start)
        {
            ll aux=0, unde=-1;
            for(int pas=1;pas<=min(20,start-poz);pas++)
            {
                ll x = calc(poz+pas,ri);
                if(x >= aux)
                {
                    aux = x;
                    unde = pas;
                }
            }
            if(aux < calc(poz,ri))
                break;
            poz+=unde;
        }
        mxm = max(mxm, calc(poz,ri));
    }*/
    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;
}
/*

intindem siru la dreapta lui start
dupa ce facem asta o sa avem: ramase = d - (ri-le)
lun + luate = d

ne fixam valoarea minima pe care o luam
0 - <lim
1 - >=lim

vrem sa luam un interval (le,ri) a.i. cnt[ri] - cnt[le-1] <= d - (ri-le)




*/

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