제출 #1154207

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1154207		alexdd	휴가 (IOI14_holiday)	C++20	24 / 100	5090 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 ramase = d - 2*(ri-start) - (start-le);
    ramase = min(ramase, (int)v.size());
    for(int i=0;i<ramase;i++)
      sum += v[i].first;
    return sum;
    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)
            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++)
    {
        while(poz+1<=start)
        {
            ll aux=0, unde=-1;
            for(int pas=1;pas<=min(24,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