Submission #100350

#	Time	Username	Problem	Language	Result	Execution time	Memory
100350		giorgosgiapis	Sličice (COCI19_slicice)	C++14	90 / 90	134 ms	2372 KiB

slicice

/*input
3 6 2
2 4 1
31 38 48 60 75 91 120
*/
#include <bits/stdc++.h>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define sz size
#define pb push_back
#define mp make_pair
using namespace std;

//#define LOCAL
#ifdef LOCAL
	#define DEBUG(x) do { cout << #x << ": " << x << '\n'; } while (0)
#else
	#define DEBUG(x) 
#endif

const double EPS = 1e-9;
const double PI = 3.141592653589793238462;

const int dr[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int dc[] = {0, 1, 1, 1, 0, -1, -1, -1};

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

typedef long long ll;

ll p[505], b[505], dp[505][505];

int main(){
	fastIo;
	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 >> b[i];
	}
	for(int i = 1; i <= n; i++){
		dp[i][0] = b[p[i]];
		for(int j = 0; j <= k; j++){
			for(int t = 0; t <= j; t++){
				if(j - t + p[i] > m) continue;
				dp[i][j] = max(dp[i][j], dp[i - 1][t] + b[p[i] + j - t]);
			}
		}
	}
	ll ans = 0;
	for(int i = 0; i <= k; i++){
		ans = max(ans, dp[n][i]);
	}
	cout << ans << '\n';

	return 0;
}

• Subtask 1: 90 / 90