oj.uz

Submission #444795

# Submission time Handle Problem Language Result Execution time Memory
444795 2021-07-15T10:24:26 Z zxcvbnm Kitchen (BOI19_kitchen) C++14
30 / 100
 567 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9 + 5;
const int maxN = 45;
bool dp[maxN][maxN*maxN][maxN*maxN];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for(int& i : a) {
        cin >> i;
    }
    for(int& i : b) {
        cin >> i;
    }

    int ans = INF;
    for(int i : a) {
        if (i < k) {
            cout << "Impossible\n";
            exit(0);
        }
    }

    int time = accumulate(a.begin(), a.end(), 0);
    dp[0][0][0] = true;
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < maxN*maxN; j++) {
            for(int p = 0; p < maxN*maxN; p++) {
                dp[i][j][p] |= dp[i-1][j][p];

                if (j-b[i-1] < 0 || p-min(n, b[i-1]) < 0) continue;
                dp[i][j][p] |= dp[i-1][j-b[i-1]][p-min(n, b[i-1])];
                if (dp[i][j][p] && j >= time && p >= k*n) {
                    ans = min(ans, j-time);
                }
            }
        }
    }

    if (ans == INF) {
        cout << "Impossible\n";
    } else {
        cout << ans << "\n";
    }
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8252 KB Output is correct
2 Correct 20 ms 8340 KB Output is correct
3 Correct 20 ms 8336 KB Output is correct
4 Correct 19 ms 8352 KB Output is correct
5 Correct 19 ms 8332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 20 ms 8280 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8252 KB Output is correct
2 Correct 20 ms 8340 KB Output is correct
3 Correct 20 ms 8336 KB Output is correct
4 Correct 19 ms 8352 KB Output is correct
5 Correct 19 ms 8332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 20 ms 8280 KB Output is correct
9 Correct 134 ms 60484 KB Output is correct
10 Correct 137 ms 60472 KB Output is correct
11 Correct 138 ms 60484 KB Output is correct
12 Correct 141 ms 60436 KB Output is correct
13 Incorrect 131 ms 60472 KB Output isn't correct

Subtask #3
0 / 20.0

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

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 376 ms 160792 KB Output is correct
2 Correct 369 ms 160776 KB Output is correct
3 Correct 370 ms 160860 KB Output is correct
4 Correct 366 ms 160792 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 8252 KB Output is correct
2 Correct 20 ms 8340 KB Output is correct
3 Correct 20 ms 8336 KB Output is correct
4 Correct 19 ms 8352 KB Output is correct
5 Correct 19 ms 8332 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 20 ms 8280 KB Output is correct
9 Correct 134 ms 60484 KB Output is correct
10 Correct 137 ms 60472 KB Output is correct
11 Correct 138 ms 60484 KB Output is correct
12 Correct 141 ms 60436 KB Output is correct
13 Incorrect 131 ms 60472 KB Output isn't correct