Submission #491211

#	Time	Username	Problem	Language	Result	Execution time	Memory
491211		blue	Feast (NOI19_feast)	C++17	100 / 100	380 ms	15376 KiB

feast

#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vi = vector<int>;
using vvi = vector<vi>;
using pll = pair<ll, ll>;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, K;
    cin >> N >> K;

    vll A(1+N);
    for(int i = 1; i <= N; i++) cin >> A[i];

    ll lo = 0, hi = 1'000'000'000'000'000'000LL;

    while(1)
    {
        ll cost = (lo+hi)/2;

        vector<pll> dp0(1+N);
        vector<pll> dp1(1+N);

        dp0[0] = {0LL, 0LL};
        dp1[0] = {-cost, -1LL};

        for(int i = 1; i <= N; i++)
        {
            dp0[i] = max(dp0[i-1], dp1[i-1]);
            dp1[i] = max(pll{dp1[i-1].first + A[i], dp1[i-1].second}, pll{dp0[i-1].first + A[i] - cost, dp0[i-1].second - 1});
        }

        pair<ll, int> X = max(dp0[N], dp1[N]);

        bool works = (-X.second <= K);

        if(lo == hi)
        {
            cout << X.first - cost*X.second << '\n';
            return 0;
        }
        else
        {
            if(works)
                hi = cost;
            else
                lo = cost+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