oj.uz

Submission #529361

# Submission time Handle Problem Language Result Execution time Memory
529361 2022-02-22T21:25:43 Z OttoTheDino Kitchen (BOI19_kitchen) C++17
100 / 100
 34 ms 712 KB 
#include <bits/stdc++.h>
using namespace std;

#define rep(i,s,e)                  for (int i = s; i <= e; ++i)
#define rrep(i,s,e)                 for (int i = s; i >= e; --i)
#define pb                          push_back
#define pf                          push_front
#define fi                          first
#define se                          second
#define all(a)                      a.begin(), a.end()
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;

const int mx = 1e5;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m, k; cin >> n >> m >> k;
    int a[n], b[m], s = 0;
    rep (i,0,n-1) {
        cin >> a[i];
        if (a[i]<k) {
            cout << "Impossible\n";
            return 0;
        }
        s += a[i];
    }
    rep (i,0,m-1) cin >> b[i];

    int dp[mx+1] = {}; //for some certain sum, what is the maximum number of different (chef, meal) pairs, if it is at least n*k and the sum is also more than the sum of ai (s), then we should have found an answer, lets see what is the minimum
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;

    rep (i,0,m-1)
        rrep (j,mx,b[i])
            if (dp[j-b[i]]!=-1) dp[j] = max(dp[j], dp[j-b[i]] + min(b[i], n));

    rep (i,s,mx) {
        if (dp[i]>=n*k) {
            cout << i-s << "\n";
            return 0;
        }
    } 

    cout << "Impossible\n";

    return 0;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 588 KB Output is correct
2 Correct 18 ms 708 KB Output is correct
3 Correct 23 ms 704 KB Output is correct
4 Correct 34 ms 588 KB Output is correct
5 Correct 23 ms 708 KB Output is correct
6 Correct 16 ms 712 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 588 KB Output is correct
2 Correct 4 ms 696 KB Output is correct
3 Correct 3 ms 588 KB Output is correct
4 Correct 3 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 588 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 588 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 1 ms 588 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 588 KB Output is correct
9 Correct 2 ms 692 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 2 ms 588 KB Output is correct
13 Correct 2 ms 588 KB Output is correct
14 Correct 19 ms 588 KB Output is correct
15 Correct 18 ms 708 KB Output is correct
16 Correct 23 ms 704 KB Output is correct
17 Correct 34 ms 588 KB Output is correct
18 Correct 23 ms 708 KB Output is correct
19 Correct 16 ms 712 KB Output is correct
20 Correct 3 ms 588 KB Output is correct
21 Correct 4 ms 696 KB Output is correct
22 Correct 3 ms 588 KB Output is correct
23 Correct 3 ms 588 KB Output is correct
24 Correct 1 ms 588 KB Output is correct
25 Correct 24 ms 588 KB Output is correct
26 Correct 21 ms 700 KB Output is correct
27 Correct 12 ms 588 KB Output is correct
28 Correct 19 ms 588 KB Output is correct
29 Correct 19 ms 700 KB Output is correct
30 Correct 23 ms 704 KB Output is correct