Submission #102228

#	Time	Username	Problem	Language	Result	Execution time	Memory
102228		IvanC	Sličice (COCI19_slicice)	C++17	90 / 90	149 ms	1428 KiB

slicice

#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;

}

• Subtask 1: 90 / 90