oj.uz

Submission #798720

# Submission time Handle Problem Language Result Execution time Memory
798720 2023-07-31T01:46:56 Z vjudge1 Kitchen (BOI19_kitchen) C++17
20 / 100
 189 ms 116900 KB 
#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];
	}
	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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116812 KB Output is correct
2 Correct 37 ms 116812 KB Output is correct
3 Correct 41 ms 116776 KB Output is correct
4 Correct 39 ms 116812 KB Output is correct
5 Correct 39 ms 116784 KB Output is correct
6 Correct 41 ms 116812 KB Output is correct
7 Incorrect 39 ms 116852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116812 KB Output is correct
2 Correct 37 ms 116812 KB Output is correct
3 Correct 41 ms 116776 KB Output is correct
4 Correct 39 ms 116812 KB Output is correct
5 Correct 39 ms 116784 KB Output is correct
6 Correct 41 ms 116812 KB Output is correct
7 Incorrect 39 ms 116852 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 116840 KB Output is correct
2 Correct 74 ms 116800 KB Output is correct
3 Correct 91 ms 116780 KB Output is correct
4 Correct 146 ms 116892 KB Output is correct
5 Correct 189 ms 116900 KB Output is correct
6 Correct 53 ms 116788 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 116824 KB Output is correct
2 Correct 39 ms 116812 KB Output is correct
3 Correct 39 ms 116812 KB Output is correct
4 Correct 41 ms 116788 KB Output is correct
5 Incorrect 40 ms 116768 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 116812 KB Output is correct
2 Correct 37 ms 116812 KB Output is correct
3 Correct 41 ms 116776 KB Output is correct
4 Correct 39 ms 116812 KB Output is correct
5 Correct 39 ms 116784 KB Output is correct
6 Correct 41 ms 116812 KB Output is correct
7 Incorrect 39 ms 116852 KB Output isn't correct
8 Halted 0 ms 0 KB -