oj.uz

Submission #102228

# Submission time Handle Problem Language Result Execution time Memory
102228 2019-03-23T17:24:55 Z IvanC Sličice (COCI19_slicice) C++17
90 / 90
 149 ms 1428 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1280 KB Output is correct
2 Correct 3 ms 1280 KB Output is correct
3 Correct 116 ms 1368 KB Output is correct
4 Correct 114 ms 1364 KB Output is correct
5 Correct 149 ms 1400 KB Output is correct
6 Correct 117 ms 1400 KB Output is correct
7 Correct 108 ms 1280 KB Output is correct
8 Correct 115 ms 1280 KB Output is correct
9 Correct 121 ms 1428 KB Output is correct
10 Correct 129 ms 1364 KB Output is correct