oj.uz

Submission #100270

# Submission time Handle Problem Language Result Execution time Memory
100270 2019-03-10T07:32:21 Z ioilolcom Sličice (COCI19_slicice) C++14
90 / 90
 207 ms 2524 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 2432 KB Output is correct
2 Correct 4 ms 2304 KB Output is correct
3 Correct 175 ms 2524 KB Output is correct
4 Correct 176 ms 2524 KB Output is correct
5 Correct 180 ms 2432 KB Output is correct
6 Correct 198 ms 2424 KB Output is correct
7 Correct 200 ms 2420 KB Output is correct
8 Correct 190 ms 2432 KB Output is correct
9 Correct 207 ms 2424 KB Output is correct
10 Correct 180 ms 2420 KB Output is correct