Submission #110252

#TimeUsernameProblemLanguageResultExecution timeMemory
110252icandoitSličice (COCI19_slicice)C++14
90 / 90
270 ms2560 KiB
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
const int N=505;
const int M=1005;
int c[M],p[M];
ll dp[N][N];
int n,m,k;
ll solve(int idx,int res){
	if(idx==n+1) {
		return 0;
	}
	if(dp[idx][res]!=-1) {
		return dp[idx][res];
	}
	ll an=0;
	for(int i=0; i<=res; i++) {
		an=max(an,c[i+p[idx]]+solve(idx+1,res-i));
	}
	return dp[idx][res]=an;
}
int main()
{
 
	ios_base:: sync_with_stdio(false); cin.tie(0);
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) {
		cin>>p[i];
	}
	for(int i=0; i<=m; i++) {
		cin>>c[i];
	}
	memset(dp,-1,sizeof dp);
	ll ans=solve(1,k);
	cout<<ans<<endl;
 
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...