Submission #1103118

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103118		haianhnguyen08102007	Feast (NOI19_feast)	C++11	100 / 100	88 ms	7516 KiB

feast

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

using namespace std;

const int N = 3e5+10;

int n, k, a[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 + a[i] - c > dp[i].first || (Max.first + a[i] - c == dp[i].first && Max.second + 1 < dp[i].second))
        {
            dp[i].first = Max.first + a[i]-c;
            dp[i].second = Max.second + 1;
        }
        if (dp[i].first - a[i] > Max.first || (dp[i].first - a[i] == Max.first && dp[i].second < Max.second))
        {
            Max.first = dp[i].first - a[i];
            Max.second = dp[i].second;
        }
    }

    return dp[n];
}

int solve()
{
    int left=1; int right=1e14;
    while (left <= right)
    {
        int mid = (left + right) / 2;
        pair <int, int> val = calculate(mid);
        if (val.second == k) return val.first + k * mid;
        if (val.second < k) right = mid - 1;
        else left = mid + 1;
    }

    pair <int, int> val = calculate(left);
    return val.first + val.second * left    ;
}

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

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

    cin>>n>>k;
    for (int i=1; i<=n; i++)
    {
        cin>>a[i]; a[i]+=a[i-1];
    }

    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