Submission #1102898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102898		Tenis0206	Feast (NOI19_feast)	C++11	100 / 100	103 ms	12888 KiB

feast

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

using namespace std;

const int nmax = 3e5;

int n,k;
int v[nmax + 5], sp[nmax + 5];

pair<int,int> dp[nmax + 5];

pair<int,int> calculate(int c)
{
    pair<int,int> Max = {0, 0};
    dp[0] = {0, 0};
    for(int i=1;i<=n;i++)
    {
        dp[i] = dp[i - 1];
        if(Max.first + sp[i] - c > dp[i].first || (Max.first + sp[i] - c == dp[i].first && Max.second + 1 < dp[i].second))
        {
            dp[i].first = Max.first + sp[i] - c;
            dp[i].second = Max.second + 1;
        }
        if(dp[i].first - sp[i] > Max.first || (dp[i].first - sp[i] == Max.first && 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 = 1e14;
    while(st<=dr)
    {
        int mij = (st + dr) >> 1;
        pair<int,int> val = calculate(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 = calculate(st);
    return val.first + val.second * st;
}

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];
    }
    cout<<solve()<<'\n';
    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