oj.uz

Submission #567200

# Submission time Handle Problem Language Result Execution time Memory
567200 2022-05-23T09:13:36 Z shrimb Kitchen (BOI19_kitchen) C++17
31 / 100
 1000 ms 213824 KB 
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991

const int maxn = 301;

int n, m, k, cntAK, cntBN, smA, smB, ans = 1e9;

int A[maxn], B[maxn];
int dp[maxn][maxn*maxn];

int rec (int i, int sm) {
    if (sm == 0) return 0;
    if (i == m || sm < 0) return -INT_MAX;
    if (dp[i][sm] != -1) return dp[i][sm];
    return max(rec(i + 1, sm), rec(i + 1, sm - B[i]) + min(B[i], n));
}

signed main () {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 0 ; i < n ; i++) {
        cin >> A[i];
        smA += A[i];
        if (A[i] < k) cntAK++;
    }
    for (int i = 0 ; i < m ; i++) {
        cin >> B[i];
        cntBN += min(n, B[i]);
        smB += B[i];
    }
    if (m < k || smB < smA || cntBN/n < k || cntAK) {
        // assert(0);
        cout << "Impossible\n";
        return 0;
    }
    memset(dp, -1, sizeof dp);
    for (int i = smA ; i < maxn * maxn ; i++) {
        if (rec(0, i) / n >= k) {
            ans = min(ans, i - smA);
            break;
        }
    }
    cout << ans << endl;
}


/*

impossible:

- M < K
- sum of B < sum of A
- the number of (B >= N) is < K
- theres an A which is < K

*/

Compilation message

kitchen.cpp:17:1: warning: multi-line comment [-Wcomment]
   17 | //\
      | ^

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 213744 KB Output is correct
2 Correct 89 ms 213660 KB Output is correct
3 Correct 84 ms 213736 KB Output is correct
4 Correct 80 ms 213676 KB Output is correct
5 Correct 95 ms 213704 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 213744 KB Output is correct
2 Correct 89 ms 213660 KB Output is correct
3 Correct 84 ms 213736 KB Output is correct
4 Correct 80 ms 213676 KB Output is correct
5 Correct 95 ms 213704 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 102 ms 213732 KB Output is correct
10 Correct 82 ms 213664 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 88 ms 213732 KB Output is correct
13 Correct 86 ms 213824 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1107 ms 213744 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1100 ms 213656 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 213744 KB Output is correct
2 Correct 89 ms 213660 KB Output is correct
3 Correct 84 ms 213736 KB Output is correct
4 Correct 80 ms 213676 KB Output is correct
5 Correct 95 ms 213704 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 102 ms 213732 KB Output is correct
10 Correct 82 ms 213664 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 88 ms 213732 KB Output is correct
13 Correct 86 ms 213824 KB Output is correct
14 Execution timed out 1107 ms 213744 KB Time limit exceeded
15 Halted 0 ms 0 KB -