Submission #969032

#	Time	Username	Problem	Language	Result	Execution time	Memory
969032		NintsiChkhaidze	Kitchen (BOI19_kitchen)	C++17	100 / 100	276 ms	24968 KiB

kitchen

#include <bits/stdc++.h>
#define ll long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
#define int ll
using namespace std;

const int N = 1e5 + 5,inf = 1e18;
int a[N],b[N],sA;
bitset <90001> dp2[305];
set <int> st[303];

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n,m,k;
	cin>>n>>m>>k;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
		sA += a[i];
		if (a[i] < k) {
			cout<<"Impossible";
			exit(0);
		}
	}

	for (int i = 1; i <= m; i++)
		cin >> b[i];

	bitset <90001> dp;
	dp[0] = 1;
	for (int i = 1; i <= m; i++){
		if (b[i] >= n) continue;
		dp |= (dp << b[i]);
	}

	dp2[0][0] = 1;
	for (int i = 1; i <= m; i++){
		if (b[i] < n) continue;

		for (int x = m; x >= 1; x--){
			dp2[x] |= (dp2[x - 1] << b[i]);
		}
	}

	for (int x=0;x<=m;x++)
		for (int s=0;s<=90000;s++)
			if (dp2[x][s]) st[x].insert(s);

	int ans = inf;
	for (int s1 = 0; s1 <= 90000; s1++){
		if (!dp[s1]) continue;

		for (int x = 0; x <= m; x++){
			if (s1 + x*n < k*n) continue;

			set <int> :: iterator it = st[x].lower_bound(sA - s1);
			if (it != st[x].end()){
				ans = min(ans,s1 + (*it) - sA);
			} 

		}
	}

	if (ans == inf){
		cout<<"Impossible";
	}else{
		cout<<ans;
	}
}

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