Submission #573566

#	Time	Username	Problem	Language	Result	Execution time	Memory
573566		danikoynov	Feast (NOI19_feast)	C++14	21 / 100	1081 ms	10556 KiB

feast

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2010;

int n, k;
ll a[maxn], dp[maxn][maxn], par[maxn];
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> a[i], par[i] = par[i - 1] + a[i];

    ll ans = 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 - 1]);
        for (int i1 = 1; i1 <= i; i1 ++)
        {
            dp[i][j] = max(dp[i][j], dp[i1 - 1][j - 1] + par[i] - par[i1 - 1]);
        }
        ans = max(ans, dp[i][j]);
    }

    cout << ans << endl;

}

int main()
{
    solve();
    return 0;
}

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