oj.uz

Submission #567018

# Submission time Handle Problem Language Result Execution time Memory
567018 2022-05-23T07:19:44 Z milisav Kitchen (BOI19_kitchen) C++14
51 / 100
 190 ms 262144 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[40][40*40][40*40];
     
    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) {
            
          	for(int i=0;i<40;i++) for(int j=0;j<40*40;j++) for(int k=0;k<40;k++) dp4[i][j][k]=-1;
            cout << rec4(0,0,0) << endl;
            return 0;
        }
    }

Compilation message

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 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 0 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 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 0 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 77 ms 107068 KB Output is correct
2 Correct 83 ms 107100 KB Output is correct
3 Correct 109 ms 107004 KB Output is correct
4 Correct 190 ms 106972 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 71 ms 107048 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 104 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 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 1 ms 212 KB Output is correct
6 Correct 1 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 0 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 77 ms 107068 KB Output is correct
15 Correct 83 ms 107100 KB Output is correct
16 Correct 109 ms 107004 KB Output is correct
17 Correct 190 ms 106972 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 71 ms 107048 KB Output is correct
20 Runtime error 104 ms 262144 KB Execution killed with signal 9
21 Halted 0 ms 0 KB -