Submission #102228

#TimeUsernameProblemLanguageResultExecution timeMemory
102228IvanCSličice (COCI19_slicice)C++17
90 / 90
149 ms1428 KiB
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 502;

int dp[MAXN][MAXN], A[MAXN], V[MAXN], N, M, K;

int solve(int n,int k){

	if(n == N + 1) return 0;
	if(dp[n][k] != -1) return dp[n][k];

	int best = 0;

	for(int qtd = 0; qtd + A[n] <= M && qtd <= k;qtd++){
		int cand = solve(n+1,k - qtd) + V[A[n] + qtd];
		best = max(best, cand);
	} 

	return dp[n][k] = best;

}

int main(){

	memset(dp, -1, sizeof(dp));
	cin >> N >> M >> K;

	for(int i = 1;i<=N;i++){
		cin >> A[i];
	}

	for(int i = 0;i<=M;i++){
		cin >> V[i];
	}

	cout << solve(1, K) << endl;

	return 0;

}
#Verdict Execution timeMemoryGrader output
Fetching results...