Submission #1103114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103114		haianhnguyen08102007	Feast (NOI19_feast)	C++17	100 / 100	104 ms	12872 KiB

feast

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

using namespace std;

const int N = 3e5+10;

int n, k, v[N], sp[N];
pair <int, int> dp[N];

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)/2;
        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;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

//    freopen("cake.inp", "r", stdin);
//    freopen("cake.out", "w", stdout);

    cin>>n>>k;
    for (int i=1; i<=n; i++)
    {
        cin>>v[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