Submission #547303

#	Time	Username	Problem	Language	Result	Execution time	Memory
547303		Stickfish	Kitchen (BOI19_kitchen)	C++17	100 / 100	172 ms	4168 KiB

kitchen

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAXN = 302;
const int SM = MAXN * 300;
int a[MAXN];
int b[MAXN];

bitset<SM> dps;
bitset<SM> dpb[MAXN];

signed main() {
    int n, m, k;
    cin >> n >> m >> k;
    int needsm = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        needsm += a[i];
        if (a[i] < k) {
            cout << "Impossible\n";
            return 0;
        }
    }
    for (int i = 0; i < m; ++i)
        cin >> b[i];
    sort(b, b + m);
    int bord = lower_bound(b, b + m, n) - b;
    dps[0] = 1;
    for (int i = 0; i < bord; ++i) {
        dps = dps | (dps << b[i]);
    }
    dpb[0][0] = 1;
    for (int i = bord; i < m; ++i) {
        for (int cnt = m; cnt > 0; --cnt) {
            dpb[cnt] |= dpb[cnt - 1] << b[i];
        }
    }
    vector<int> sms_arr;
    for (int sms = 0; sms < SM; sms = dps._Find_next(sms))
        sms_arr.push_back(sms);
    sms_arr.push_back(SM);
    int ans = SM;
    for (int cnt = 0; cnt <= m; ++cnt) {
        int is = sms_arr.size() - 1;
        for (int smb = 0; smb < SM; smb = dpb[cnt]._Find_next(smb)) {
            while (is > 0 && (sms_arr[is - 1] + smb >= needsm && sms_arr[is - 1] >= n * (k - cnt)))
                --is;
            //cout << "(" << cnt << ' ' << smb << "): " << sms_arr[is] << endl;
            ans = min(ans, sms_arr[is] + smb);
        }
    }
    if (ans < SM) {
        cout << ans - needsm << '\n';
    } else {
        cout << "Impossible\n";
    }
}

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