제출 #745886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
745886		vjudge1	Kitchen (BOI19_kitchen)	C++17	100 / 100	49 ms	1036 KiB

kitchen

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

#define int long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second

void imp() {
    cout << "Impossible";
    cout << "\n";
    exit(0);
}

int n, m, k;
vector<int> a, b;
int sum_a;

/*int try_4(int idx) {
    int pref = 0;
    for(int i = 0; i <= idx; i++) {
        pref += b[i];
    }
    if(pref < sum_a) {
        return -1;
    }
    int sum1 = 0;
    for(int i = 0; i <= idx; i++) {
        sum1 += min(n, b[idx]);
    }
    if(sum1 < n * k) {
        return -1;
    }
    return pref - sum_a;
}*/

void solve() {
    cin >> n >> m >> k;
    a.resize(n), b.resize(m);
    for(int &x : a) {
        cin >> x;
        sum_a += x;
    }
    sort(a.begin(), a.end());
    for(int &x : b) {
        cin >> x;
    }
    sort(b.begin(), b.end());
    reverse(b.begin(), b.end());
    for(int i = 0; i < n; i++) {
        if(a[i] < k) {
            imp();
        }
    }
    /*int l = -1, r = m;
    bool possible = false;
    int result = -42;
    while(l < r - 1) {
        int mid = (l + r) / 2;
        int res = try_4(mid);
        if(res != -1 && (result == -42 || result > res)) {
            result = res;
        }
        if(res != -1) {
            r = mid;
        } else {
            l = mid;
        }
    }
    if(r == m) {
        imp();
    }
    cout << result << "\n";*/
    int maxx = 300 * 300;
    vector<int> dp(1 + maxx, 0);
    vector<bool> is(1 + maxx, false);
    is[0] = true;
    for(int i = 1; i <= m; i++) {
        int val = b[i - 1];
        int other_val = min(b[i - 1], n);
        for(int j = maxx; j >= val; j--) {
            if(is[j - val]) {
                is[j] = true;
                dp[j] = max(dp[j], dp[j - val] + other_val);
            }
        }
    }
    for(int i = sum_a; i <= maxx; i++) {
        if(is[i] && dp[i] >= n * k) {
            cout << i - sum_a << "\n";
            return;
        }
    }
    imp();
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}

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