Submission #642656

#	Time	Username	Problem	Language	Result	Execution time	Memory
642656		aebov	Kitchen (BOI19_kitchen)	C++17	0 / 100	18 ms	980 KiB

kitchen

#include<iostream>
#include<vector>
#include<bitset>
#include<algorithm>
#include<cstring>
#define ll long long
#define pb push_back
using namespace std;

ll inf = (ll)1e18 + 18;
const int N = 302;
ll int n, m, k , sum , sum2;
ll int a[N], b[N];
ll ans = inf;
ll dp[N*N + N + N + 2];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 1 ; i <= n; i ++){
		cin >> a[i], sum += a[i];
		if( a[i] < k){
			cout << "Impossible\n";
			return 0;
		}
	}
	for(int i = 1 ; i <= m; i ++) cin >> b[i], sum2 += b[i];
	if( sum2 < sum){
		cout << "Impossible\n";
		return 0;
	}
	sort(b + 1 , b + m + 1);
	memset(dp,-1,sizeof(dp));
	dp[0] = 0 ;
	for(int i = m ; i ; i--) {
        for(int j = N*N - b[i]  ; j >= 0; j--) {
            if(dp[j] != -1)dp[j + b[i]] = max(dp[j + b[i]] , dp[j] + min(n, b[i]));
        }
    }
	for(int i = sum; i <= N*N; i++){
		if(dp[i] >= n*k) cout << i-sum << "\n";
		return 0;
	}
	cout << "Impossible\n";
}

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