Submission #861141

#	Time	Username	Problem	Language	Result	Execution time	Memory
861141		sleepntsheep	Feast (NOI19_feast)	C++17	12 / 100	28 ms	6272 KiB

feast

#include <cstdio>
#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;
        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 dp[N]{0};
        memset(dp, -0xbf, sizeof dp);
        dp[0] = 0;
        for (int i = 1; i <= n; ++i) dp[i] = max({0ll, 1ll*a[i], dp[i-1] + a[i]});
        return cout <<*max_element(dp, dp+N), 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]);
                }
            } }
        cout << dp[n][k];
    }

    return 0;
}

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:34:59: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |         if (k == 1) return cout << max({p[x-1], p[n] - p[x], p[n]}), 0;
      |                                                        ~~~^

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