Submission #764661

#	Time	Username	Problem	Language	Result	Execution time	Memory
764661		Meloric	Kitchen (BOI19_kitchen)	C++17	100 / 100	30 ms	980 KiB

kitchen

#include <bits/stdc++.h>
#define pb push_back
#define int int64_t
#define pii pair<int, int>
#define X first
#define Y second
#define all(x) (x).begin(),(x).end()
#define lb lower_bound
#define ub upper_bound

using namespace std;

const int inf = 1e9;

void p(auto A){
	for(auto e : A)cout << e << ' ';
	cout << '\n';
}
void solve(){
	int n, m, k; cin >> n >> m >> k;
	vector<int>A(n), B(m);
	for(int i = 0; i< n; i++)cin >> A[i];
	for(int i = 0; i< m; i++)cin >> B[i];
	
	for(auto e : A)if(e < k){
		cout << "Impossible";
		return;
	}
	
	int tot = accumulate(all(B), 0);
	vector<int> dp(tot+5, -inf);
	dp[0] = 0;
	
	auto xmax = [](int& a, int b){a=max(a, b);};
	
	for(int i = 0; i< m; i++){
		for(int j = tot-B[i]; j >= 0; j--){
			xmax(dp[j+B[i]], dp[j]+min(n, B[i]));
		}
	}
	
	int sma = accumulate(all(A), 0);
	for(int i = sma; i<= tot; i++){
		if(dp[i] >= k*n){
			cout << i-sma;
			return;
		}
	}
	
	cout << "Impossible";
}

signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int t = 1;
	//cin >> t;
	while(t--)solve();
}

Compilation message (stderr)

kitchen.cpp:15:8: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   15 | void p(auto A){
      |        ^~~~

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