Submission #1212813

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212813		Dan4Life	Kitchen (BOI19_kitchen)	C++20	100 / 100	28 ms	1096 KiB

kitchen

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define pb push_back
#define int long long
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
using ll = long long;
using vi = vector<int>;
using ar2 = array<int,2>;
using ar3 = array<int,3>;
 
const int mxN = (int)3e2+2;
const int INF = (int)1e9;
const ll LINF = (ll)2e18;
const int MOD = (int)1e9+7;
const int mxLg = 20;
 
int dp[mxN*mxN];
int n, m, k, tot;
int a[mxN], b[mxN], c[mxN];
 
int32_t main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> k; int ans = INF;
    for(int i = 1; i < mxN*mxN; i++) dp[i] = -INF;
    for(int i = 1; i <= n; i++) cin >> a[i],tot+=a[i];
    for(int i = 1; i <= m; i++) cin >> b[i], c[i]=min(n,b[i]);
    for(int i = 1; i <= m; i++){
		for(int j = mxN*mxN-1; j >= b[i]; j--){
			dp[j] = max(dp[j], dp[j-b[i]]+c[i]);
			if(j>=tot and dp[j]>=n*k) ans=min(ans, j);
		}
	}
	if(ans==INF or *min_element(a+1,a+n+1)<k) cout << "Impossible";
	else cout << ans-tot;
	cout << "\n";
}

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