Submission #110252

#	Time	Username	Problem	Language	Result	Execution time	Memory
110252		icandoit	Sličice (COCI19_slicice)	C++14	90 / 90	270 ms	2560 KiB

slicice

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

• Subtask 1: 90 / 90