Submission #977587

#	Time	Username	Problem	Language	Result	Execution time	Memory
977587		efedmrlr	Kitchen (BOI19_kitchen)	C++17	0 / 100	110 ms	7392 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<bitset<N * 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(i, N) REP(j, N * N) {
        dp2[i][j] = 0;
    }
    REP(i, sum + 1) {
        if(dp1[i]) {
            int x = i / n;
            x = min(x, k);
            dp2[x][i - x * n] = 1;
        }
    }
    for(int i = mid + 1; i <= m; i++) {
        for(int j = 0; j <= k; j++) {
            for(int s = 0; s <= bsum; s++) {
                dp2n[j][s] = dp2[j][s];
                if(j > 0 && s - (b[i] - n) >= 0) {
                    dp2n[j][s] = dp2n[j][s] | dp2[j - 1][s - (b[i] - n)];
                }
                if(s - b[i] >= 0) {
                    dp2n[j][s] = dp2n[j][s] | dp2[j][s - b[i]];
                }
            }
        }
        swap(dp2, dp2n);
    }
    sum -= n * k;
    for(int s = sum; s <= bsum; s++) {
        if(dp2[k][s]) {
            cout << s - sum << "\n";
            return;
        }
    }
    cout << "Impossible\n";
}

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

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