oj.uz

Submission #863426

# Submission time Handle Problem Language Result Execution time Memory
863426 2023-10-20T08:49:09 Z ArashJafariyan Kitchen (BOI19_kitchen) C++17
52 / 100
 201 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 300 + 1;

short int n, m, k, a[N], b[N];
bitset<N * N> dp[N * N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m >> k;
    bool ok = 1;
    int s = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] < k)
            ok = 0;
        s += a[i];
    }
    for (int i = 0; i < m; i++)
        cin >> b[i];

    if (!ok) {
        cout << "Impossible";
        return 0;
    }

    dp[0][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = n * m; j >= 0; j--)
            dp[j + min(b[i], n)] |= (dp[j] << b[i]);
    }

    int ans = INT_MAX;
    for (int i = n * k; i <= n * m; i++) 
        for (int j = s; j <= m * N; j++)
            if (dp[i][j])
                ans = min(ans, j);

    if (ans == INT_MAX)
        cout << "Impossible";
    else
        cout << ans - s;

    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 1 ms 736 KB Output is correct
5 Correct 5 ms 8028 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 480 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 1 ms 736 KB Output is correct
5 Correct 5 ms 8028 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 480 KB Output is correct
9 Correct 4 ms 2008 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 8 ms 2908 KB Output is correct
12 Correct 16 ms 5556 KB Output is correct
13 Correct 201 ms 51548 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 140 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 12376 KB Output is correct
2 Correct 87 ms 11608 KB Output is correct
3 Correct 141 ms 16108 KB Output is correct
4 Correct 158 ms 18256 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 2808 KB Output is correct
4 Correct 1 ms 736 KB Output is correct
5 Correct 5 ms 8028 KB Output is correct
6 Correct 0 ms 480 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 480 KB Output is correct
9 Correct 4 ms 2008 KB Output is correct
10 Correct 3 ms 1116 KB Output is correct
11 Correct 8 ms 2908 KB Output is correct
12 Correct 16 ms 5556 KB Output is correct
13 Correct 201 ms 51548 KB Output is correct
14 Runtime error 140 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -