Submission #1193698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193698		repsak	Feast (NOI19_feast)	C++20	0 / 100	290 ms	327680 KiB

feast

// https://oj.uz/problem/view/NOI19_feast
// O(N*K) solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
    int N, K;
    cin >> N >> K;

    vector<int> values(N);
    for(int i = 0; i < N; i++){
        cin >> values[i];
    }

    // N * K * 2
    ll MAX = 1e18;
    vector<vector<vector<ll>>> score(N, vector<vector<ll>>(K + 1, vector<ll>(2, 0)));
    score[0][1][1] = values[0];
    // score[0][1][0] = values[0];

    for(int i = 1; i < N; i++){
        for(int j = 0 + 1; j < K + 1; j++){
            int val = values[i];
            // l = 1 (During) 
            score[i][j][1] = max({  
                // score[i][j][1], 
                score[i - 1][j][1] + val,
                score[i - 1][j - 1][0] + val
            });

            // l = 0 (Ended)
            score[i][j][0] = max({
                // score[i][j][0],
                score[i - 1][j][1]
            });
        }
    }

    ll best = 0;
    for(int i = 0; i <= K; i++){
        best = max({best, score[N - 1][i][0], score[N - 1][i][1]});
    }

    cout << best;
}

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