oj.uz

Submission #567014

# Submission time Handle Problem Language Result Execution time Memory
567014 2022-05-23T07:16:55 Z milisav Kitchen (BOI19_kitchen) C++14
51 / 100
 143 ms 107060 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 dp3[maxn][maxn*maxn];
int dp4[41][41*41][41*41];
 
int rec3 (int i, int sm) {
    if (sm >= smA) return sm - smA;
    if (i == m) return 1e9;
    if (dp3[i][sm] != -1) return dp3[i][sm];
    return dp3[i][sm] = min(rec3(i + 1, sm), rec3(i + 1, sm + B[i]));
}
 
int rec4 (int i, int sm, int sm2) {
    if (i == m) {
        if (sm >= smA and sm2/n >= k) return sm - smA;
        return 1e9;
    }
    if (dp4[i][sm][sm2] != -1) return dp4[i][sm][sm2];
    return dp4[i][sm][sm2] = max(rec4(i + 1, sm, sm2), rec4(i + 1, sm + B[i], sm2 + 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;
    }
    if (m <= 15) { // subtasks 1 and 2
        for (int i = 0 ; i < (1 << m) ; i++) {
            smB = 0, cntBN = 0;
            if (__builtin_popcount(i) < k) continue;
            for (int j = 0 ; j < m ; j++) {
                if (i & (1 << j)) {
                    smB += B[j];
                    cntBN += min(n, B[j]);
                }
            }
            if (smB >= smA and cntBN/n >= k) ans = min(ans, smB - smA);
        }
        cout << ans << endl;
        return 0;
    }
    if (k == 1) {
        memset(dp3, -1, sizeof dp3);
        cout << rec3(0, 0) << endl;
        return 0;
    }
    if (max({n, m, k, *max_element(A, A+n), *max_element(B,B+m)}) <= 40) {

      	cout<<"ok"<<endl;
        return 0;
        memset(dp4, -1, sizeof dp4);
        cout << rec4(0,0,0) << endl;
        return 0;
    }
}

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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
22.0 / 22.0

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

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 107056 KB Output is correct
2 Correct 61 ms 107052 KB Output is correct
3 Correct 85 ms 107060 KB Output is correct
4 Correct 143 ms 107060 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 74 ms 107052 KB Output is correct

Subtask #4
0 / 21.0

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

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 68 ms 107056 KB Output is correct
15 Correct 61 ms 107052 KB Output is correct
16 Correct 85 ms 107060 KB Output is correct
17 Correct 143 ms 107060 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 74 ms 107052 KB Output is correct
20 Incorrect 1 ms 212 KB Output isn't correct
21 Halted 0 ms 0 KB -