Submission #1143851

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143851		borisAngelov	Feast (NOI19_feast)	C++20	18 / 100	138 ms	7456 KiB

feast

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300'007
long long ar[MAXN],dp[MAXN],sub[MAXN];
int n,k;
void makedp(long long wanda)
{
    dp[1]=max(max(0LL,wanda),ar[1]+wanda);
    if (dp[1]==(ar[1]+wanda)) sub[1]=1;
    else if (dp[1]==wanda) sub[1]=1;
    else sub[1]=0;
    long long mks=ar[1];
    long long koi=0;
    for (int q=2;q<=n;q++)
    {
        if (dp[q-1]>mks)
        {
            mks=dp[q-1];
            koi=q-1;
        }
        mks+=ar[q];
        dp[q]=max( mks+wanda, max( dp[q-1] , dp[q-1]+wanda ) );
        if (dp[q]==mks+wanda)
        {
            sub[q]=sub[koi]+1;
        }
        else if (dp[q]==dp[q-1])
        {
            sub[q]=sub[q-1];
        }
        else sub[q]=sub[q-1]+1;
    }
}
int main()
{
    cin>>n>>k;
    for (int q=1;q<=n;q++) cin>>ar[q];
    long long l=-30000000000000,r=0;
    while (l<r-1)
    {
        long long mid=(l+r)/2;
        makedp(mid);
        //cout<<mid<<" "<<dp[n]<<" "<<sub[n]<<"\n";
        if (sub[n]<=k) l=mid;
        else r=mid;
    }
    makedp(l);
    cout<<(dp[n]-l*k)<<"\n";
}

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