Submission #1320937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320937		d_k	Kitchen (BOI19_kitchen)	C++20	100 / 100	17 ms	1056 KiB

kitchen

							/*Bismillahir Rahmanir Raheem*/
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define pb push_back

const int inf = (1LL << 60);
const int N = 303;

void ma1n() {
	int n, m, k;
	cin>>n>>m>>k;
	vector<int> a(n + 1), b(m + 1);
	int suma = 0, sumb = 0;
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		suma += a[i];
		if(a[i] < k) {
			cout<<"Impossible\n";
			return;
		}
	}
	
	for(int i = 1; i <= m; i++) {
		cin>>b[i];
		sumb+=b[i];
	}
	
	if (sumb < suma){
        cout << "Impossible\n";
        return;
    }
	vector<int> dp(sumb + 1, -1);
	int need = k * n; dp[0] = 0;
	for(int i = 1; i <= m; i++){
		int take = min(b[i], n);
		for(int j = sumb; j >= b[i]; j--){
			if (dp[j - b[i]] != -1) dp[j] = max(dp[j], dp[j - b[i]] + take);
		}
	}
	int ans = inf;
	for(int i = suma; i <= sumb; i++){
		if(dp[i] >= need) {
			cout<<i - suma<<"\n";
			return;
		}
	}
	cout<<"Impossible\n";
	return;
}

main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	int T = 1;
//	cin>>T;
	while(T--) {
		ma1n();
	}
}

Compilation message (stderr)

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

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