oj.uz

Submission #200099

# Submission time Handle Problem Language Result Execution time Memory
200099 2020-02-05T10:23:58 Z Saboon Sličice (COCI19_slicice) C++14
90 / 90
 161 ms 504 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 152 ms 376 KB Output is correct
4 Correct 155 ms 376 KB Output is correct
5 Correct 158 ms 504 KB Output is correct
6 Correct 155 ms 504 KB Output is correct
7 Correct 149 ms 376 KB Output is correct
8 Correct 161 ms 376 KB Output is correct
9 Correct 149 ms 376 KB Output is correct
10 Correct 158 ms 376 KB Output is correct