oj.uz

Submission #977587

# Submission time Handle Problem Language Result Execution time Memory
977587 2024-05-08T07:22:19 Z efedmrlr Kitchen (BOI19_kitchen) C++17
0 / 100
 110 ms 7392 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7392 KB Output is correct
2 Correct 46 ms 7252 KB Output is correct
3 Correct 52 ms 7380 KB Output is correct
4 Correct 48 ms 7252 KB Output is correct
5 Incorrect 45 ms 5088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7392 KB Output is correct
2 Correct 46 ms 7252 KB Output is correct
3 Correct 52 ms 7380 KB Output is correct
4 Correct 48 ms 7252 KB Output is correct
5 Incorrect 45 ms 5088 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 110 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 7276 KB Output is correct
2 Correct 52 ms 7260 KB Output is correct
3 Correct 45 ms 5088 KB Output is correct
4 Incorrect 45 ms 4944 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 7392 KB Output is correct
2 Correct 46 ms 7252 KB Output is correct
3 Correct 52 ms 7380 KB Output is correct
4 Correct 48 ms 7252 KB Output is correct
5 Incorrect 45 ms 5088 KB Output isn't correct
6 Halted 0 ms 0 KB -