Submission #567018

#TimeUsernameProblemLanguageResultExecution timeMemory
567018milisavKitchen (BOI19_kitchen)C++14
51 / 100
190 ms262144 KiB
    #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 (stderr)

kitchen.cpp:17:5: warning: multi-line comment [-Wcomment]
   17 |     //\
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...