oj.uz

Submission #938764

# Submission time Handle Problem Language Result Execution time Memory
938764 2024-03-05T14:03:06 Z vjudge1 Kitchen (BOI19_kitchen) C++17
51 / 100
 76 ms 3472 KB 
#include <bits/stdc++.h>
#define int long long
#define M 302
 
using namespace std;
 
int n, m, k, A = 0, B = 0, res = -1;
bool flag = false;
vector<int> a, b;
vector<vector<bool>> dp;
 
signed main() {
    cin >> n >> m >> k;
    a = vector<int>(n), b = vector<int>(m);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        A += a[i];
        if(a[i] < k) flag = true;
    }
    for(int i = 0; i < m; i++) {
        cin >> b[i];
        B += b[i];
    }
    if(k > 1 || m <= 15) {
       // try every subset
    vector<int> diff;
    bitset<M> bin;
    int sus, sum;
    bool check;
    for(int i = 0; i < (1 << m); i++) {
        sum = 0, sus = 0;
        for(int j = 0; j < m; j++) {
            if(i & (1 << j)) {
                sum += b[j];
                sus += min(n, b[j]);
            }
        }
        if(sum >= A && sus >= n * k) {
            if(res == -1) res = sum - A;
            else res = min(res, sum - A);
        }
    }
    if(flag || res == -1) cout << "Impossible\n";
    else cout << res << "\n";
    } else {
    dp = vector<vector<bool>>(m + 1, vector<bool>(B + 1, false));
    dp[0][0] = true;
    for(int i = 1; i <= m; i++) {
        for(int j = 0; j <= B; j++) {
            if(j >= b[i - 1]) dp[i][j] = dp[i - 1][j] | dp[i - 1][j - b[i - 1]];
            //cout << dp[i][j] << " ";
        }
        //cout << "\n";
    }
    //
    int res = LLONG_MAX;
    for(int i = 0; i <= m; i++) {
        for(int j = A; j <= B; j++) {
            if(dp[i][j]) res = min(res, j - A);
        }
    }
    if(res == LLONG_MAX) cout << "Impossible\n";
    else cout << res << "\n";}
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:29:10: warning: unused variable 'check' [-Wunused-variable]
   29 |     bool check;
      |          ^~~~~

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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 2396 KB Output is correct
2 Correct 38 ms 1884 KB Output is correct
3 Correct 41 ms 2140 KB Output is correct
4 Correct 71 ms 3472 KB Output is correct
5 Correct 76 ms 3416 KB Output is correct
6 Correct 30 ms 1628 KB Output is correct

Subtask #4
0 / 21.0

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

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 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 344 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 2 ms 344 KB Output is correct
13 Correct 2 ms 348 KB Output is correct
14 Correct 53 ms 2396 KB Output is correct
15 Correct 38 ms 1884 KB Output is correct
16 Correct 41 ms 2140 KB Output is correct
17 Correct 71 ms 3472 KB Output is correct
18 Correct 76 ms 3416 KB Output is correct
19 Correct 30 ms 1628 KB Output is correct
20 Incorrect 0 ms 344 KB Output isn't correct
21 Halted 0 ms 0 KB -