oj.uz

Submission #509576

# Submission time Handle Problem Language Result Execution time Memory
509576 2022-01-14T07:01:49 Z kianaRZV Kitchen (BOI19_kitchen) C++14
100 / 100
 157 ms 222424 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define int long long

using namespace std;

const int maxn = 305, inf = 1e9 + 9;
int n, m, k, ans = inf, sum;
int a[maxn], b[maxn], dp[maxn][maxn * maxn];
bool check = false;

void read_input() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        check |= (a[i] < k);
    }
    for (int i = 1; i <= m; i++)
        cin >> b[i];
}

void solve() {
    memset(dp, -63, sizeof(dp));
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++)
        for (int j = 0; j < maxn * maxn; j++) {
            dp[i][j] = dp[i - 1][j];
            if (j - b[i] >= 0)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - b[i]] + min(n, b[i]));
            if (j >= sum && dp[i][j] >= n * k)
                ans = min(ans, j - sum);
        }
    if (check || ans >= inf)
        cout << "Impossible";
    else
        cout << ans;
}

int32_t main() {
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    read_input(), solve();
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 222296 KB Output is correct
2 Correct 78 ms 222324 KB Output is correct
3 Correct 88 ms 222356 KB Output is correct
4 Correct 83 ms 222276 KB Output is correct
5 Correct 93 ms 222388 KB Output is correct
6 Correct 93 ms 222388 KB Output is correct
7 Correct 81 ms 222332 KB Output is correct
8 Correct 84 ms 222396 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 222296 KB Output is correct
2 Correct 78 ms 222324 KB Output is correct
3 Correct 88 ms 222356 KB Output is correct
4 Correct 83 ms 222276 KB Output is correct
5 Correct 93 ms 222388 KB Output is correct
6 Correct 93 ms 222388 KB Output is correct
7 Correct 81 ms 222332 KB Output is correct
8 Correct 84 ms 222396 KB Output is correct
9 Correct 85 ms 222372 KB Output is correct
10 Correct 87 ms 222280 KB Output is correct
11 Correct 83 ms 222348 KB Output is correct
12 Correct 83 ms 222412 KB Output is correct
13 Correct 86 ms 222272 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 222284 KB Output is correct
2 Correct 130 ms 222400 KB Output is correct
3 Correct 123 ms 222316 KB Output is correct
4 Correct 138 ms 222392 KB Output is correct
5 Correct 132 ms 222396 KB Output is correct
6 Correct 114 ms 222348 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 222424 KB Output is correct
2 Correct 86 ms 222276 KB Output is correct
3 Correct 95 ms 222336 KB Output is correct
4 Correct 90 ms 222316 KB Output is correct
5 Correct 87 ms 222352 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 222296 KB Output is correct
2 Correct 78 ms 222324 KB Output is correct
3 Correct 88 ms 222356 KB Output is correct
4 Correct 83 ms 222276 KB Output is correct
5 Correct 93 ms 222388 KB Output is correct
6 Correct 93 ms 222388 KB Output is correct
7 Correct 81 ms 222332 KB Output is correct
8 Correct 84 ms 222396 KB Output is correct
9 Correct 85 ms 222372 KB Output is correct
10 Correct 87 ms 222280 KB Output is correct
11 Correct 83 ms 222348 KB Output is correct
12 Correct 83 ms 222412 KB Output is correct
13 Correct 86 ms 222272 KB Output is correct
14 Correct 135 ms 222284 KB Output is correct
15 Correct 130 ms 222400 KB Output is correct
16 Correct 123 ms 222316 KB Output is correct
17 Correct 138 ms 222392 KB Output is correct
18 Correct 132 ms 222396 KB Output is correct
19 Correct 114 ms 222348 KB Output is correct
20 Correct 84 ms 222424 KB Output is correct
21 Correct 86 ms 222276 KB Output is correct
22 Correct 95 ms 222336 KB Output is correct
23 Correct 90 ms 222316 KB Output is correct
24 Correct 87 ms 222352 KB Output is correct
25 Correct 127 ms 222396 KB Output is correct
26 Correct 148 ms 222340 KB Output is correct
27 Correct 105 ms 222328 KB Output is correct
28 Correct 114 ms 222332 KB Output is correct
29 Correct 117 ms 222368 KB Output is correct
30 Correct 157 ms 222400 KB Output is correct