Submission #931289

#	Time	Username	Problem	Language	Result	Execution time	Memory
931289		andrei_boaca	Feast (NOI19_feast)	C++17	100 / 100	111 ms	29144 KiB

feast

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const ll INF=1e17;
ll n,k,v[600005];
struct date
{
    ll val,l,r;
};
date dp[600005][2];
date combine(date a, date b)
{
    if(a.val>b.val)
        return a;
    if(a.val<b.val)
        return b;
    a.l=min(a.l,b.l);
    a.r=max(a.r,b.r);
    return a;
}
date calc(ll cost)
{
    dp[0][0]={0,0,0};
    dp[0][1]={-INF,0,0};
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=combine(dp[i-1][0],dp[i-1][1]);
        date a=dp[i-1][0];
        a.l++;
        a.r++;
        a.val+=v[i]-cost;
        dp[i][1]=a;
        a=dp[i-1][1];
        a.val+=v[i];
        dp[i][1]=combine(dp[i][1],a);
        a=dp[i-1][1];
        a.l++;
        a.r++;
        a.val+=v[i]-cost;
        dp[i][1]=combine(dp[i][1],a);
    }
    return combine(dp[n][0],dp[n][1]);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(ll i=1;i<=n;i++)
        cin>>v[i];
    n+=k;
    ll st=-1e12;
    ll dr=1e12;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        date rez=calc(mij);
        if(rez.l<=k&&rez.r>=k)
        {
            cout<<rez.val+k*mij;
            return 0;
        }
        if(rez.l>k)
            st=mij+1;
        else
            dr=mij-1;
    }
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29