제출 #1225172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225172		nguyn	Kitchen (BOI19_kitchen)	C++20	100 / 100	16 ms	584 KiB

kitchen

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 305;
const int inf = 300 * 300;

int n, m, k;
int a[N];
int b[N];
int f[N * N];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    int mn = 1e9;
    int suma = 0;
    int sumb = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        suma += a[i];
        mn = min(mn, a[i]);
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        sumb += b[i];
    }

    if (mn < k) {
        cout << "Impossible";
        return 0;
    }
    for (int i = 1; i <= inf; i++) f[i] = -inf;
    f[0] = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = sumb; j >= b[i]; j--) {
            f[j] = max(f[j], f[j - b[i]] + min(b[i], n));
        }
    }
    for (int i = suma; i <= inf; i++) {
        if (f[i] >= n * k) {
            cout << i - suma;
            return 0;
        }
    }
    cout << "Impossible";
}

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