Submission #200099

#	Time	Username	Problem	Language	Result	Execution time	Memory
200099		Saboon	Sličice (COCI19_slicice)	C++14	90 / 90	161 ms	504 KiB

slicice

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;

const int maxn = 500 + 10;

ll dp[3][maxn], p[maxn], cost[maxn];

int main(){
	ios_base::sync_with_stdio(false);
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++)
		cin >> p[i];
	for (int i = 0; i <= m; i++)
		cin >> cost[i];
	
	for (int i = 1; i <= n; i++){
		int idx = i % 2;
		for (int j = 0; j <= k; j++)
			for (int q = 0; q <= j and p[i] + q <= m; q++)
				dp[idx][j] = max(dp[idx][j], dp[1 - idx][j - q] + cost[p[i] + q]);
		for (int j = 0; j <= k; j++)
			dp[1 - idx][j] = 0;
	}
	ll answer = 0;
	for (int i = 0; i <= k; i++)
		answer = max(answer, dp[n % 2][i]);
	cout << answer << endl;
}

• Subtask 1: 90 / 90