제출 #784156

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
784156		raysh07	Kitchen (BOI19_kitchen)	C++17	100 / 100	11 ms	600 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;
#define INF (int)1e9
#define f first
#define s second

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve()
{
	int n, m, k; cin >> n >> m >> k;

	vector <int> a(n), b(m);
	int sum = 0;
	for (auto &x : a) {
		cin >> x;
		sum += x;
		if (x < k){
			cout << "Impossible\n";
			return;
		}
	}

	for (auto &x : b) cin >> x;

	vector <int> dp(m * 300 + 1, -INF);
	dp[0] = 0;
	int cnt = 0;

	for (auto x : b){
		cnt += 300;
		for (int i = cnt; i >= x; i--){
			dp[i] = max(dp[i], dp[i - x] + min(x, n));
		}
	}

	for (int i = sum; i <= m * 300; i++){
		if (dp[i] >= k * n){
			cout << i - sum << "\n";
			return;
		}
	}

	cout << "Impossible\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;

   // freopen("in",  "r", stdin);
   // freopen("out", "w", stdout);

  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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