oj.uz

Submission #110252

# Submission time Handle Problem Language Result Execution time Memory
110252 2019-05-10T10:26:40 Z icandoit Sličice (COCI19_slicice) C++14
90 / 90
 270 ms 2560 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2560 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 168 ms 2552 KB Output is correct
4 Correct 171 ms 2424 KB Output is correct
5 Correct 174 ms 2432 KB Output is correct
6 Correct 200 ms 2552 KB Output is correct
7 Correct 182 ms 2432 KB Output is correct
8 Correct 236 ms 2508 KB Output is correct
9 Correct 270 ms 2552 KB Output is correct
10 Correct 255 ms 2432 KB Output is correct