Submission #977618

#	Time	Username	Problem	Language	Result	Execution time	Memory
977618		efedmrlr	Kitchen (BOI19_kitchen)	C++17	100 / 100	93 ms	1400 KiB

kitchen

#include <bits/stdc++.h>

#define lli long long int
#define ld long double
#define pb push_back
#define MP make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.begin(), x.end()
#define REP(i, n) for(int i = 0; (i) < (n); (i)++)

using namespace std;

void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int N = 305;
const int INF = 1e9 + 500;
const int MOD = 1e9 + 7;

bitset<N * N> dp1, dp1n;
array<int, N * N> dp2, dp2n;
int n, m, k;
int sum = 0;
vector<int> a, b;
void solve() {
    cin >> n >> m >> k;
    a.resize(n + 1, 0);
    b.assign(m + 1, 0);
    bool f = 0;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] < k) f = 1;
        sum += a[i];
    }
    int mid = 0;
    int bsum = 0;
    for(int i = 1; i <= m; i++) {
        cin >> b[i];
        bsum += b[i];
        if(b[i] <= n) mid++;
    }
    if(f) {
        cout << "Impossible\n";
        return;
    }

    sort(all(b));
    REP(i, N * N) {
        dp1[i] = 0;
    }
    dp1[0] = 1;
    for(int i = 1; i <= mid; i++) {
        for(int j = 0; j <= bsum; j++) {
            dp1n[j] = dp1[j];
            if(j - b[i] >= 0) {
                dp1n[j] = dp1n[j] | dp1[j - b[i]];
            }
        }
        swap(dp1, dp1n);
    }
    REP(j, N * N) {
        dp2[j] = -1;
    }
    REP(i, bsum + 1) {
        if(dp1[i]) {
            int x = i / n;
            dp2[i] = max(x, dp2[i]);
        }
    }
    for(int i = mid + 1; i <= m; i++) {
        for(int s = 0; s <= bsum; s++) {
            dp2n[s] = dp2[s];
            if(s - b[i] >= 0 && dp2[s - b[i]] != -1) {
                dp2n[s] = max(dp2n[s], dp2[s - b[i]] + 1);
            }
        }
        swap(dp2, dp2n);
    }
    for(int s = sum; s <= bsum; s++) {
        if(dp2[s] >= k) {
            cout << s - sum << "\n";
            return; 
        }
    }
    cout << "Impossible\n";
}

signed main() {
    fastio();
    solve();
}

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