oj.uz

Submission #530122

# Submission time Handle Problem Language Result Execution time Memory
530122 2022-02-24T16:24:09 Z fatemetmhr Kitchen (BOI19_kitchen) C++17
51 / 100
 23 ms 460 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb     push_back
#define fi     first
#define se     second
#define all(x) x.begin(), x.end()

const int maxn5 = 7e3 + 10;
const ll  inf   = 1e18;
const int masum = 1e5 + 10;

ll a[maxn5], b[maxn5];
ll n, m, k;
bool dp[masum];

inline void solve(){
	dp[0] = true;
	for(int i = 0; i < m; i++){
		for(int j = masum - 1; j >= b[i]; j--){
			dp[j] |= dp[j - b[i]];
		}
	}
	ll sum = 0;
	for(int i = 0; i < n; i++)
		sum += a[i];
	for(int i = sum; i < masum; i++) if(dp[i]){
		cout << i - sum << '\n';
		exit(0);
	}
	cout << "Impossible" << endl;
	exit(0);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	

	cin >> n >> m >> k;
	ll sum = 0;
	for(int i = 0; i < n; i++){
		cin >> a[i];
		if(a[i] < k)
			return cout << "Impossible" << endl, 0;
		sum += a[i];
	}
	for(int i = 0; i < m; i++)
		cin >> b[i];
	if(m > 16 || k == 1)
		solve();
	ll ans = inf;
	for(int mask = 0; mask < (1 << m); mask++) if(__builtin_popcount(mask) >= k){
		ll sum1 = 0, sum2 = 0;
		for(int i = 0; i < m; i++) if((mask >> i)&1){
			sum1 += min(n, b[i]);
			sum2 += b[i];
		}
		if(sum1 >= n * k && sum2 >= sum && ans >= sum2){
			ans = sum2;
			//cout << mask << ' ' << sum1 << ' ' << sum2 << endl;
		}
	}
	if(ans == inf)
		cout << "Impossible" << endl;
	else
		cout << ans - sum << endl;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 428 KB Output is correct
2 Correct 16 ms 316 KB Output is correct
3 Correct 23 ms 324 KB Output is correct
4 Correct 20 ms 412 KB Output is correct
5 Correct 22 ms 460 KB Output is correct
6 Correct 17 ms 432 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 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 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 19 ms 428 KB Output is correct
15 Correct 16 ms 316 KB Output is correct
16 Correct 23 ms 324 KB Output is correct
17 Correct 20 ms 412 KB Output is correct
18 Correct 22 ms 460 KB Output is correct
19 Correct 17 ms 432 KB Output is correct
20 Incorrect 3 ms 332 KB Output isn't correct
21 Halted 0 ms 0 KB -