oj.uz

Submission #100322

# Submission time Handle Problem Language Result Execution time Memory
100322 2019-03-10T11:43:50 Z ozneroL Sličice (COCI19_slicice) C++14
90 / 90
 135 ms 2436 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 117 ms 2432 KB Output is correct
4 Correct 128 ms 2432 KB Output is correct
5 Correct 117 ms 2432 KB Output is correct
6 Correct 115 ms 2424 KB Output is correct
7 Correct 109 ms 2432 KB Output is correct
8 Correct 113 ms 2436 KB Output is correct
9 Correct 106 ms 2420 KB Output is correct
10 Correct 135 ms 2424 KB Output is correct