Submission #209819

#	Time	Username	Problem	Language	Result	Execution time	Memory
209819		Alexa2001	Feast (NOI19_feast)	C++17	100 / 100	307 ms	10876 KiB

feast

#include <bits/stdc++.h>

using namespace std;

/// 17:28

typedef long long ll;
const int Nmax = 3e5 + 5, lim = 1e9;

pair<ll, int> dp[Nmax][2];
int a[Nmax], n, k;

pair<ll,int> best(pair<ll, int> a, pair<ll, int> b)
{
    if(a.first == b.first) return a.second < b.second ? a : b;
    return a.first > b.first ? a : b;
}

pair<ll, int> operator - (pair<ll, int> a, ll x)
{
    return {a.first - x, a.second + 1};
}

pair<ll, int> operator + (pair<ll, int> a, ll x)
{
    return {a.first + x, a.second};
}

pair<ll, int> solve(ll cost)
{
    int i;
    dp[0][0] = dp[0][1] = {0, 0};

    for(i=1; i<=n; ++i)
    {
        dp[i][0] = best(dp[i-1][0], dp[i-1][1] - cost);
        dp[i][1] = best(dp[i-1][0], dp[i-1][1]) + a[i];
    }
    return best(dp[n][0], dp[n][1] - cost);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

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

    ll mid, st = 0, dr = (ll) n * lim;

    while(st <= dr)
    {
        mid = (st + dr) / 2;
        if(solve(mid).second > k) st = mid + 1;
            else dr = mid - 1;
    }

    cout << solve(st).first + (ll) k * st << '\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