oj.uz

Submission #314457

# Submission time Handle Problem Language Result Execution time Memory
314457 2020-10-20T01:04:55 Z shrek12357 Sličice (COCI19_slicice) C++14
90 / 90
 159 ms 384 KB 
#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <string>
	#include <map>
	#include <set>
	#include <climits>
	#include <cmath>
	#include <fstream>
	#include <queue>
	#include <stack>
	#include <bitset>
	using namespace std;
	#define ll long long
	//cin.tie(0);ios_base::sync_with_stdio(0); 

	const int MAXN = 505;

	vector<int> dp(MAXN);

	int main() {
		int n, m, k;
		cin >> n >> m >> k;
		vector<int> curs;
		for (int i = 0; i < n; i++) {
			int temp;
			cin >> temp;
			curs.push_back(temp);
		}
		vector<int> vals;
		for (int i = 0; i < m + 1; i++) {
			int temp;
			cin >> temp;
			vals.push_back(temp);
		}
		for (int i = 0; i < n; i++) {
			vector<int> temp(MAXN);
			for (int j = 0; j <= k; j++) {
				for(int a = 0; a <= m; a++){
					if (a > j) {
						break;
					}
					if (curs[i] + a > m) {
						break;
					}
					int val = vals[curs[i] + a];
					temp[j] = max(dp[j - a] + val, temp[j]);
				}
			}
			dp = temp;
		}
		cout << dp[k] << endl;
	}

Subtask #1
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 155 ms 376 KB Output is correct
4 Correct 155 ms 376 KB Output is correct
5 Correct 154 ms 376 KB Output is correct
6 Correct 153 ms 376 KB Output is correct
7 Correct 148 ms 376 KB Output is correct
8 Correct 159 ms 376 KB Output is correct
9 Correct 146 ms 376 KB Output is correct
10 Correct 158 ms 376 KB Output is correct