Submission #1270223

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270223		windowwife	Feast (NOI19_feast)	C++20	100 / 100	110 ms	8672 KiB

feast

#include<bits/stdc++.h>
#define ll long long
#define task ""
using namespace std;
const ll maxn = 1e6 + 2, inf = 1e18;
int k, n, a[maxn], cnt[maxn][2];
ll l = 0, r = inf, m, dp[maxn][2];
bool check (ll m)
{
    for (int i = 1; i <= n; i++)
    {
        dp[i][0] = dp[i - 1][0];
        cnt[i][0] = cnt[i - 1][0];
        if (dp[i][0] < dp[i - 1][1])
        {
            dp[i][0] = dp[i - 1][1];
            cnt[i][0] = cnt[i - 1][1];
        }
        else if (dp[i][0] == dp[i - 1][1]) cnt[i][0] = max(cnt[i][0], cnt[i - 1][1]);

        dp[i][1] = dp[i - 1][0] + a[i] - m;
        cnt[i][1] = cnt[i - 1][0] + 1;
        if (dp[i][1] < dp[i - 1][1] + a[i])
        {
            dp[i][1] = dp[i - 1][1] + a[i];
            cnt[i][1] = cnt[i - 1][1];
        }
        else if (dp[i][1] == dp[i - 1][1] + a[i]) cnt[i][1] = max(cnt[i][1], cnt[i - 1][1]);
    }
    if (dp[n][0] > dp[n][1]) return cnt[n][0] >= k;
    else if (dp[n][0] < dp[n][1]) return cnt[n][1] >= k;
    else return max(cnt[n][0], cnt[n][1]) >= k;
}
int main()
{
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    dp[0][1] = -inf;
    while (l <= r)
    {
        m = (l + r)/2;
        if (check(m)) l = m + 1;
        else r = m - 1;
    }
    check(max(r, 0LL));
    cout << max(r, 0LL)*k + max(dp[n][0], dp[n][1]);
}

• 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