Submission #100322

#	Time	Username	Problem	Language	Result	Execution time	Memory
100322		ozneroL	Sličice (COCI19_slicice)	C++14	90 / 90	135 ms	2436 KiB

slicice

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

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;


#define F first
#define S second

#define ERR 1e-9

#if !ONLINE_JUDGE && !EVAL
    #define dbg_var(x) cerr << #x << ": " << x << "\n";
    #define dbg_iter(x, y) cerr  << #x << ": " << print_iterable(x, y) << "\n";
#else
    #define dbg_var(x)
    #define dbg_iter(x, y)
#endif // ONLINE_JUDGE

template <typename T1, typename T2>
string print_iterable( T1 begin_iter, T2 end_iter){
    bool first = true;
    stringstream res;
    res << "[ ";
    for(; begin_iter != end_iter; ++begin_iter){
        if(!first) res << ", ";
        first = false;
        res << *begin_iter;
    }
    res << " ]";
    return res.str();
}

void aggMax(ll & res, ll x){ if(x > res)res = x; }
void aggMin(ll & res, ll x){ if(x < res)res = x; }

ll II(){ ll i; cin >> i; return i; }
void OI(ll i){ cout << i; }

// constraints
const ll MAXN = 510;
ll N, M, K, images[MAXN], points[MAXN+1];
ll memo[MAXN][MAXN];

ll solve(ll actualTeam, ll remainingK){
    if(memo[actualTeam][remainingK] != -1) return memo[actualTeam][remainingK];
    if(actualTeam == N) return 0;
    ll res = 0;
    for(ll i=0; i<=remainingK && (images[actualTeam]+i<=M); i++){
        ll act_points = points[images[actualTeam] + i];

        ll res_tmp = solve(actualTeam+1, remainingK-i);
        res = max(res, act_points+res_tmp);
    }
    return memo[actualTeam][remainingK] = res;
}

int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    N = II(); M = II(); K = II();

    for(ll i = 0; i<N; i++) images[i] = II();
    for(ll i=0; i<M+1; i++) points[i] = II();

    memset(memo, -1, sizeof memo);
    cout << solve(0, K);

    return 0;
}

• Subtask 1: 90 / 90