oj.uz

Submission #100350

# Submission time Handle Problem Language Result Execution time Memory
100350 2019-03-10T13:30:13 Z giorgosgiapis Sličice (COCI19_slicice) C++14
90 / 90
 134 ms 2372 KB 
/*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.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2304 KB Output is correct
2 Correct 4 ms 2304 KB Output is correct
3 Correct 128 ms 2296 KB Output is correct
4 Correct 122 ms 2296 KB Output is correct
5 Correct 125 ms 2296 KB Output is correct
6 Correct 125 ms 2372 KB Output is correct
7 Correct 127 ms 2336 KB Output is correct
8 Correct 131 ms 2296 KB Output is correct
9 Correct 121 ms 2296 KB Output is correct
10 Correct 134 ms 2268 KB Output is correct