제출 #861159

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861159		sleepntsheep	Feast (NOI19_feast)	C++17	51 / 100	182 ms	262144 KiB

feast

#include <cstdio>
#include <climits>
#include <functional>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;

#define N 300005
#define ALL(x) x.begin(), x.end()

int n, k, a[N];
long long p[N];

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i], p[i] = p[i-1] + a[i];

    if (count_if(a+1, a+1+n,[](int x){ return x<0; }) == 0) return cout << accumulate(a+1,a+1+n, 0ll), 0;

    if (count_if(a+1, a+1+n,[](int x){ return x<0; }) == 1)
    {
        int x=0;
        for (int i = 1; i <= n; ++i) if (a[i] < 0) x = i;
        if (k == 1) return cout << max({p[x-1], p[n] - p[x], p[n]}), 0;
        else return cout << p[n] - a[x], 0;
    }

    if (k == 1)
    {
        long long ans = 0, mn = 0;
        for (int i = 1; i <= n; ++i) ans = max(ans, p[i] - mn), mn = min(mn, p[i]);
        return cout << ans, 0;
    }

    if (n <= 300)
    {
        long long dp[305][305]{0};
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= k; ++j)
            {
                dp[i][j] = max({dp[i-1][j], dp[i][j], dp[i][j-1]});
                for (int l = 0; l < i; ++l) dp[i][j] = max(dp[i][j], dp[l][j-1] + p[i] - p[l]);
            }
        return cout << dp[n][k], 0;
    }

    if (n <= 3000)
    {
        vector<vector<vector<long long>>> dp(3005, vector<vector<long long>>(3005, vector<long long>(2)));

        long long ans = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= k; ++i)
            {
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]);
                dp[i][j][1] = max({a[i] + dp[i-1][j-1][0], a[i] + dp[i-1][j][1]});
                ans = max({ans, dp[i][j][0], dp[i][j][1]});
            }
        }
        return cout << ans, 0;
    }

    //assert(0);
#if 0
    {
        function<void(int, int, int, int, int)> compute = [&](int i, int l, int r, int optl, int optr)
        {
            if (l > r) return;
            int m = (l+r)/2;
            pair<long long, int> best = {LLONG_MIN, -1};
            for (int k = optl; k <= min(m, optr); ++k)
                best = max(best, {(dp[!(i&1)][k]) + p[m] - p[k], k});
            dp[i&1][m] = best.first;
            compute(i, l, m-1, optl, best.second), compute(i, m+1, r, best.second, optr);
        };

        long long ans = 0;
        for (int i = 1; i <= k; ++i)
        {
            compute(i, 1, n, 0, n-1);
            for (int i = 1; i <= n; ++i) dp[i&1][i] = max(dp[i&1][i], dp[i&1][i-1]);
            ans = max(ans, *max_element(dp[i&1], dp[i&1]+n+1));
        }
        return cout << ans,0;
    }
#endif

    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29