Submission #798722

#	Time	Username	Problem	Language	Result	Execution time	Memory
798722		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	190 ms	116940 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int totA;
int A[310], B[310];
int dp[310][310*310];

int f(int m, int t) {
	if (m==0) {
		if (t==0) return 0;
		else return -1e9;
	}
	int& res = dp[m][t];
	if (res != -1) return res;
	res = max(f(m-1,t), f(m-1,t-B[m])+min(N,B[m]));
//	cout << m << " " << t << " " << res << endl;
	return res;
}


int main() {
	cin >> N >> M >> K;
	for(int i=1; i<=N; i++) {
		cin >> A[i];
		totA += A[i];
		if (A[i] < K) {
			cout << "Impossible" << endl;
			return 0;
		}
	}
	for(int i=1; i<=M; i++) {
		cin >> B[i];
	}
	memset(dp, -1, sizeof(dp));
	for(int i=totA; i<=300*300; i++) {
//		cout << i << " " << f(N,i) << endl;
		if (f(M, i) >= N*K) {
			cout << i-totA << endl;
			return 0;
		}
	}
	cout << "Impossible" << endl;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 20 / 20
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28