oj.uz

Submission #840337

# Submission time Handle Problem Language Result Execution time Memory
840337 2023-08-31T10:01:04 Z serifefedartar Kitchen (BOI19_kitchen) C++17
20 / 100
 97 ms 106344 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) {cout << #x << ": "; for (auto it : x) cout << it << " ";cout << enl;}
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 305

int dp[MAXN][90005];
vector<int> meal, chef;
int main() {
	fast
	int N, M, K; 
	cin >> N >> M >> K;

	meal = vector<int>(N+1);
	chef = vector<int>(M+1);
	int sum = 0;
	for (int i = 1; i <= N; i++) {
		cin >> meal[i]; 
		sum += meal[i];
	}
	for (int i = 1; i <= M; i++)
		cin >> chef[i];

	for (int i = 0; i <= M; i++) {
		for (int total = 0; total <= 90000; total++)
			dp[i][total] = -1e8;
	}
	dp[0][0] = 0;
	
	for (int i = 1; i <= M; i++) {
		for (int total = 0; total <= 90000; total++) {
			dp[i][total] = dp[i-1][total];
			if (total - chef[i] >= 0)
				dp[i][total] = max(dp[i][total], dp[i-1][total - chef[i]] + min(chef[i], N)); 		
		}
	}

	int ans = INT_MAX;
	for (int total = sum; total <= 90000; total++) {
		if (dp[M][total] >= N * K)
			ans = min(ans, total - sum);
	}

	if (ans == INT_MAX)
		cout << "Impossible\n";
	else
		cout << ans << "\n"; 
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Incorrect 1 ms 1364 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Incorrect 1 ms 1364 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 91 ms 92512 KB Output is correct
2 Correct 72 ms 80232 KB Output is correct
3 Correct 97 ms 106344 KB Output is correct
4 Correct 89 ms 106260 KB Output is correct
5 Correct 85 ms 102756 KB Output is correct
6 Correct 64 ms 73928 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 14680 KB Output is correct
2 Correct 18 ms 14764 KB Output is correct
3 Correct 16 ms 14764 KB Output is correct
4 Correct 17 ms 14772 KB Output is correct
5 Incorrect 15 ms 14752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1364 KB Output is correct
2 Correct 1 ms 1364 KB Output is correct
3 Correct 1 ms 1364 KB Output is correct
4 Correct 1 ms 1364 KB Output is correct
5 Correct 1 ms 1364 KB Output is correct
6 Correct 1 ms 1364 KB Output is correct
7 Incorrect 1 ms 1364 KB Output isn't correct
8 Halted 0 ms 0 KB -