oj.uz

Submission #863005

# Submission time Handle Problem Language Result Execution time Memory
863005 2023-10-19T12:57:02 Z ArashJafariyan Kitchen (BOI19_kitchen) C++17
52 / 100
 312 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 300 + 4;

int n, m, k, a[N], b[N];
bitset<N * N> dp[N * N], save[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 = 0; j <= m * n; j++) 
            save[j] = dp[j];
        for (int j = 0; j <= m * n; j++)
            dp[j + min(b[i], n)] |= (save[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 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 8 ms 18268 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 8 ms 18268 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 7 ms 5980 KB Output is correct
10 Correct 6 ms 5468 KB Output is correct
11 Correct 14 ms 9404 KB Output is correct
12 Correct 26 ms 14052 KB Output is correct
13 Correct 312 ms 106832 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 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 199 ms 26964 KB Output is correct
2 Correct 214 ms 26460 KB Output is correct
3 Correct 256 ms 35076 KB Output is correct
4 Correct 284 ms 41308 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2800 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 8 ms 18268 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 7 ms 5980 KB Output is correct
10 Correct 6 ms 5468 KB Output is correct
11 Correct 14 ms 9404 KB Output is correct
12 Correct 26 ms 14052 KB Output is correct
13 Correct 312 ms 106832 KB Output is correct
14 Runtime error 41 ms 262144 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -