Submission #1102947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102947		filiptudose7	Feast (NOI19_feast)	C++11	100 / 100	95 ms	12368 KiB

feast

#include <bits/stdc++.h>
#define int long long
using namespace std;
int sp[300005],v[300005];
pair <int,int> dp[300005];
int n,k;
pair <int,int> calc(int lambda)
{
    pair<int,int> Max={0,0};

    for(int i=1; i<=n; ++i)
    {
        dp[i]=dp[i-1];
        if(Max.first+sp[i]-lambda>dp[i].first || (Max.first+sp[i]-lambda==dp[i].first && Max.second+1<dp[i].second))
        {
            dp[i].first=Max.first+sp[i]-lambda;
            dp[i].second=Max.second+1;
        }
        if(dp[i].first>Max.first+sp[i] || (dp[i].first==Max.first+sp[i] && dp[i].second<Max.second))
        {
            Max.first=dp[i].first-sp[i];
            Max.second=dp[i].second;
        }
    }
    return dp[n];
}
int solve()
{
    int st=1;
    int dr=3e14;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        pair<int,int> val=calc(mij);
        if(val.second==k)
        {
            return val.first+k*mij;
        }
        if(val.second<k)dr=mij-1;
        else st=mij+1;
    }
    pair<int,int> val=calc(st);
    return val.first+val.second*st;
}
signed main()
{
    ///freopen("feast.in","r",stdin);
    ///freopen("feast.out","w",stdout);
    cin.sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; ++i)cin>>v[i];
    for(int i=1; i<=n; ++i)sp[i]=sp[i-1]+v[i];
    cout<<solve();
    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