Kickstart 2020, Round A, Plates

bruteforce.cpp

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

#define sz 55
#define ll long long int

int plate_beauty[sz][sz];

int max_beauty(int curr_stk, int K, int plates_left){
    if(plates_left <= 0 || curr_stk < 0){
        return 0;
    }
    int max_b = max_beauty(curr_stk-1, K, plates_left), cur_b=0;
    for(int i=0; i<min(plates_left, K); i++){
        cur_b += plate_beauty[curr_stk][i];
        max_b = max(cur_b + max_beauty(curr_stk-1, K, plates_left-i-1), max_b);
    }
    return max_b;
}

int main()
{
    int T;
    cin>>T;
    for(int tnum=1; tnum <= T; tnum ++){
        int N, K, P;
        cin>>N>>K>>P;

        for(int stk=0; stk<N; stk++){
            for(int plate=0; plate<K; plate++){
                cin>>plate_beauty[stk][plate];
            }
        }
        cout<<"Case #"<<tnum<<": "<<max_beauty(N-1, K, P)<<"\n";
    }
    return 0;
}

memoized.cpp

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

#define sz 55
#define ll long long int

int plate_beauty[sz][sz];
int dp[sz][2005];

int max_beauty(int curr_stk, int K, int plates_left){
    if(plates_left <= 0 || curr_stk < 0){
        return 0;
    }
    if(dp[curr_stk][plates_left] != -1){
        return dp[curr_stk][plates_left];
    }
    int max_b = max_beauty(curr_stk-1, K, plates_left), cur_b=0;
    for(int i=0; i<min(plates_left, K); i++){
        cur_b += plate_beauty[curr_stk][i];
        max_b = max(cur_b + max_beauty(curr_stk-1, K, plates_left-i-1), max_b);
    }
    dp[curr_stk][plates_left] = max_b;
    return max_b;
}

int main()
{
    int T;
    cin>>T;
    for(int tnum=1; tnum <= T; tnum ++){
        int N, K, P;
        cin>>N>>K>>P;

        for(int stk=0; stk<N; stk++){
            for(int plate=0; plate<K; plate++){
                cin>>plate_beauty[stk][plate];
            }
        }
        memset(dp, -1, sizeof(dp));
        cout<<"Case #"<<tnum<<": "<<max_beauty(N-1, K, P)<<"\n";
    }
    return 0;
}