oj.uz

Submission #921378

# Submission time Handle Problem Language Result Execution time Memory
921378 2024-02-03T18:19:57 Z penguin133 Kitchen (BOI19_kitchen) C++17
29 / 100
 42 ms 111464 KB 
#include <bits/stdc++.h>
using namespace std;
 
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
int memo[305][305][605], A[305], B[305], dp2[305][305], n, m, k, mx, mn = 1e9, ans = 2e9, sm;
 
int dp(int x, int y, int cur){
	if(x == m + 1){
		if(cur < mx || y < k)return 2e9;
		return (cur >= mx ? cur  - sm : 2e9);
	}
	if(memo[x][y][cur] != -1)return memo[x][y][cur];
	if(cur >= mx){
		return memo[x][y][cur] = (dp2[x][max(0, k - y)] + cur) - sm;
	}
	return memo[x][y][cur] = min(dp(x + 1, y, cur), dp(x + 1, y + 1, cur + B[x]));
}
*/
int n, m, k, A[305], B[305], mx, mn = 1e9, sm, dp[305][305*305 + 300];
 
void solve(){
	cin >> n >> m >> k;
	for(int i = 1; i <= n; i++)cin >> A[i], mx = max(mx, A[i]), sm += A[i], mn = min(mn, A[i]);
	if(mn < k){
		cout << "Impossible\n";
		return;
	}
	for(int i = 1; i <= m; i++)cin >> B[i];
	/*
	dp2[m+1][0] = 0;
	for(int i = 1; i <= m; i++)dp2[m+1][i] = 2e9;
	for(int i = m; i >= 1; i--){
		for(int j = 0; j <= m; j++){
			dp2[i][j] = min(dp2[i+1][j], (j ? dp2[i+1][j-1] + B[i] : (int)1e18));
		} 
	}
	memset(memo, -1, sizeof(memo));
	int res = dp(1, 0, 0);
	if(res > 1e9)cout << "Impossible\n";
	else cout << res << '\n';
	*/
	dp[0][0] = 0;
	for(int i = 1; i <= 300 * 300; i++)dp[0][i] = -2e9;
	for(int i = 1; i <= m; i++){
		for(int j = 0; j <= 300 * 300; j++){
			dp[i][j] = max(dp[i-1][j], (j >= B[i] ? dp[i - 1][j - B[i]] + 1 : (int)-1e18));
		}
	}
	for(int i = sm; i <= 300 * 300; i++){
		if(dp[m][i] >= k){
			cout << i - sm << '\n';
			return;
		}
	}
	cout << "Impossible";
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message

kitchen.cpp:67:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   67 | main(){
      | ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Incorrect 3 ms 6748 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 96860 KB Output is correct
2 Correct 37 ms 84560 KB Output is correct
3 Correct 41 ms 111464 KB Output is correct
4 Correct 42 ms 111432 KB Output is correct
5 Correct 39 ms 107092 KB Output is correct
6 Correct 30 ms 78420 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 16984 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 3 ms 6748 KB Output is correct
10 Correct 3 ms 6748 KB Output is correct
11 Incorrect 3 ms 6748 KB Output isn't correct
12 Halted 0 ms 0 KB -