Submission #1102955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102955		Tenis0206	Feast (NOI19_feast)	C++11	12 / 100	60 ms	14416 KiB

feast

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int oo = 0x3f3f3f3f;

int n,k;
int v[300005];
int sp[300005];

pair<int,int> dp[300005][2];

pair<int,int> get_val(int c)
{
    /* int Max = 0, nrval = 0;
     int Max_pref = 0, nrval_pref = 0;
     for(int i=1;i<=n;i++)
     {
         dp[i].first = Max_pref + sp[i] - c;
         dp[i].second = nrval_pref + 1;
         if(dp[i].first > Max || (dp[i].first==Max && dp[i].second < nrval))
         {
             Max = dp[i].first;
             nrval = dp[i].second;
         }
         if(Max - sp[i] > Max_pref || (Max - sp[i]==Max_pref && nrval < nrval_pref))
         {
             Max_pref = Max - sp[i];
             nrval_pref = nrval;
         }
     }
     */
    dp[0][1].first = -oo;
    for(int i=1; i<=n+1; i++)
    {
        if(dp[i-1][0]>=dp[i-1][1])
        {
            dp[i][0] = dp[i-1][0];
        }
        else
        {
            dp[i][0] = dp[i-1][1];
        }
        if(pair<int,int>{dp[i-1][1].first + v[i], 0 - dp[i-1][1].second} >= pair<int,int>{dp[i-1][0].first + v[i] - c, 0 - (dp[i-1][0].second + 1)})
        {
            dp[i][1] = {dp[i-1][1].first + v[i], dp[i-1][1].second};
        }
        else
        {
            dp[i][1] = {dp[i-1][0].first + v[i] - c, dp[i-1][0].second + 1};
        }
    }
    return dp[n+1][0];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
        sp[i] = sp[i-1] + v[i];
    }
    int st = 1;
    int dr = 1e15;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1LL;
        pair<int,int> val = get_val(mij);
        if(val.second==k)
        {
            cout<<val.first + k * mij<<'\n';
            return 0;
        }
        if(val.second<k)
        {
            dr = mij - 1;
        }
        else
        {
            st = mij + 1;
        }
    }
    pair<int,int> val = get_val(st);
    cout<<val.first + val.second * st<<'\n';
    return 0;
}

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