Submission #1140694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140694		Esgeer	Feast (NOI19_feast)	C++20	59 / 100	216 ms	327680 KiB

feast

#include <bits/stdc++.h>
using namespace std;
#define F(i, s, e) for(int i = s; i < e; i++)
#define vi vector<int>
#define pb push_back
#define int long long
#define sp <<' '<<

const int inf = 1e15;

void solve() {
    int n, k;
    cin >> n >> k;
    int a[n];
    F(i, 0, n) cin >> a[i];
    int dp[n][k+1][2];
    F(i, 0, n) F(j, 0, k+1) F(l, 0, 2) dp[i][j][l] = -inf;
    dp[0][0][0] = 0;
    dp[0][1][1] = a[0];

    F(i, 1, n) {
        F(j, 0, k+1) {
            dp[i][j][0] = max(max(dp[i-1][j][0], dp[i-1][j][1]), j ? dp[i][j-1][0] : -inf);
            dp[i][j][1] = max(max(j ? dp[i-1][j-1][0] : -inf, dp[i-1][j][1]) + a[i], j ? dp[i][j-1][1] : -inf);
        }
    }

    cout << max(dp[n-1][k][0], dp[n-1][k][1]) << endl;
}

int32_t main() {
    #ifdef Local
        freopen("io.in", "r", stdin);
        freopen("io.out", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while(t--) solve();
}

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