Submission #1193721

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193721		repsak	Feast (NOI19_feast)	C++20	59 / 100	227 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 N, K;
vector<int> values(N);

ll slow(ll index, ll score, ll kUsed, ll inRun){
    if(kUsed > K) return 0;
    if(index == N){
        return score;
    }

    ll kInc = 1;
    if(inRun) kInc = 0;
    
    return max({
        slow(index + 1, score, kUsed, 0),
        slow(index + 1, score + values[index], kUsed + kInc, 1)
    });
}

ll solve(int N, int K){
    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];

    ll best = 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],
                score[i - 1][j][0]
            });

            best = max({
                best,
                score[i][j][1],
                score[i][j][0]
            });
        }
    }

    return best;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> N >> K;

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

    ll res = solve(N, K);
    cout << res;
    
    // ll a = 0; ll b = 0;

    // while(a == b){
    //     N = rand() % 10 + 2;
    //     K = rand() % 10 + 1;

    //     values.resize(N);
        
    //     for(int i = 0; i < N; i++){
    //        values[i] = rand() % 100 - rand() % 150; 
    //     }

    //     a = slow(0, 0, 0, 0);
    //     b = solve(N, K);

    //     cout << a << " = " << b << "\n";
    // }
}

• 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