oj.uz

Submission #100424

# Submission time Handle Problem Language Result Execution time Memory
100424 2019-03-11T08:23:49 Z heon Sličice (COCI19_slicice) C++17
90 / 90
 493 ms 1528 KB 
#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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1408 KB Output is correct
2 Correct 6 ms 1408 KB Output is correct
3 Correct 340 ms 1528 KB Output is correct
4 Correct 347 ms 1408 KB Output is correct
5 Correct 290 ms 1408 KB Output is correct
6 Correct 294 ms 1420 KB Output is correct
7 Correct 493 ms 1448 KB Output is correct
8 Correct 465 ms 1528 KB Output is correct
9 Correct 268 ms 1500 KB Output is correct
10 Correct 311 ms 1528 KB Output is correct