Submission #100424

#	Time	Username	Problem	Language	Result	Execution time	Memory
100424		heon	Sličice (COCI19_slicice)	C++17	90 / 90	493 ms	1528 KiB

slicice

#include<bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
typedef vector <int> vi;
typedef pair<int,int> ii;
typedef long long ll;

const int mod = 1e9 + 7;
const ll inf = 3e18 + 5;

int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
int mul(int a, int b) { return 1LL * a * b % mod; }

int n, m, p[505], b[505], dp[505][505];

int f(int i, int k){
	if(k < 0) return -mod;
	if(i == n) return 0;
	if(dp[i][k] != -1) return dp[i][k];
	int ret = 0;
	for(int j = p[i]; j < m + 1; j++){
		ret = max(ret, (b[j] - b[p[i]]) + f(i + 1, k - (j - p[i])));
	}
	return dp[i][k] = ret;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
  
	int k;
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++)
		cin >> p[i];
	for(int i = 0; i < m + 1; i++)
		cin >> b[i];
	memset(dp, -1, sizeof dp);
	int res = 0;
	for(int i = 0; i < n; i++)
		res += b[p[i]];
	cout << f(0, k) + res;
}

• Subtask 1: 90 / 90