oj.uz

Submission #584347

# Submission time Handle Problem Language Result Execution time Memory
584347 2022-06-27T08:43:23 Z talant117408 Kitchen (BOI19_kitchen) C++17
100 / 100
 65 ms 110500 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define long                unsigned long 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define rall(v)             (v).rbegin(),(v).rend()
#define lb                  lower_bound
#define ub                  upper_bound
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'

vector <bitset <100001>> dp(301);

void impossible() {
    cout << "Impossible" << endl;
    exit(0);
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector <int> a(n), b(m+1);
    for (auto &to : a) cin >> to;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    int dishes = 0, chefs = 0;
    for (auto to : a) dishes += to;
    if (*min_element(all(a)) < k) impossible();
    
    vector <vector <int>> dp(m+1, vector <int> (90000 + 1, -2e9));
    dp[0][0] = 0;
    
    for (int i = 1; i <= m; i++) {
        chefs += b[i];
        for (int j = chefs; j >= 0; j--) {
            if (j >= b[i])
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - b[i]] + min(n, b[i]));
            else dp[i][j] = dp[i - 1][j];
        }
    }
    for (int j = dishes; j <= chefs; j++) {
        if (dp[m][j] >= n * k) {
            cout << j - dishes;
            return;
        }
    }
    
    impossible();
}

int main() {
    do_not_disturb
    
    int t = 1;
    //~ cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5332 KB Output is correct
4 Correct 2 ms 5332 KB Output is correct
5 Correct 2 ms 5328 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 2 ms 3924 KB Output is correct
8 Correct 2 ms 5368 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5332 KB Output is correct
4 Correct 2 ms 5332 KB Output is correct
5 Correct 2 ms 5328 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 2 ms 3924 KB Output is correct
8 Correct 2 ms 5368 KB Output is correct
9 Correct 4 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 4 ms 9952 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 96688 KB Output is correct
2 Correct 41 ms 84300 KB Output is correct
3 Correct 53 ms 110476 KB Output is correct
4 Correct 62 ms 110412 KB Output is correct
5 Correct 58 ms 106884 KB Output is correct
6 Correct 50 ms 77972 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18772 KB Output is correct
2 Correct 8 ms 18772 KB Output is correct
3 Correct 8 ms 18744 KB Output is correct
4 Correct 8 ms 18772 KB Output is correct
5 Correct 2 ms 3924 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5332 KB Output is correct
2 Correct 3 ms 5332 KB Output is correct
3 Correct 2 ms 5332 KB Output is correct
4 Correct 2 ms 5332 KB Output is correct
5 Correct 2 ms 5328 KB Output is correct
6 Correct 2 ms 3924 KB Output is correct
7 Correct 2 ms 3924 KB Output is correct
8 Correct 2 ms 5368 KB Output is correct
9 Correct 4 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 5 ms 9940 KB Output is correct
12 Correct 4 ms 9952 KB Output is correct
13 Correct 5 ms 9940 KB Output is correct
14 Correct 54 ms 96688 KB Output is correct
15 Correct 41 ms 84300 KB Output is correct
16 Correct 53 ms 110476 KB Output is correct
17 Correct 62 ms 110412 KB Output is correct
18 Correct 58 ms 106884 KB Output is correct
19 Correct 50 ms 77972 KB Output is correct
20 Correct 9 ms 18772 KB Output is correct
21 Correct 8 ms 18772 KB Output is correct
22 Correct 8 ms 18744 KB Output is correct
23 Correct 8 ms 18772 KB Output is correct
24 Correct 2 ms 3924 KB Output is correct
25 Correct 40 ms 78644 KB Output is correct
26 Correct 46 ms 90292 KB Output is correct
27 Correct 32 ms 61140 KB Output is correct
28 Correct 53 ms 90684 KB Output is correct
29 Correct 58 ms 92872 KB Output is correct
30 Correct 65 ms 110500 KB Output is correct