Submission #1154166

#	Time	Username	Problem	Language	Result	Execution time	Memory
1154166		alexdd	Holiday (IOI14_holiday)	C++20	7 / 100	5094 ms	1620 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];
ll calc(int le, int 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());

    ll sum=0;
    int mnm=INF, ramase = d - 2*(ri-start);
    for(int i=0;i<v.size();i++)
    {
        mnm = min(mnm, v[i].second);
        if(ramase - (start-mnm) < i+1)
            break;
        sum += v[i].first;
    }
    return sum;
}
ll solve()
{
    ll mxm=0;
    /*int le=1;
    for(int ri=start;ri<=n;ri++)
    {
        while(le+1<=start && calc(le+1,ri) >= calc(le,ri))
            le++;
        mxm = max(mxm, calc(le,ri));
    }*/
    for(int le=start;le>0;le--)
        for(int ri=start;ri<=n;ri++)
            mxm = max(mxm, calc(le,ri));
    int poz=1;
    for(int ri=start;ri<=n;ri++)
    {
        ll cv=-1;
        int unde=-1;
        for(int i=poz;i<=start;i++)
        {
            int x = calc(i,ri);
            if(x > cv)
            {
                cv = x;
                unde = i;
            }
        }
        mxm = max(mxm, cv);
        poz = unde;
    }
    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: 0 / 17
• Subtask 4: 0 / 53