oj.uz

답안 #567023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
567023 2022-05-23T07:22:45 Z shrimb Kitchen (BOI19_kitchen) C++17
72 / 100
 671 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[40][40*40][40*40];
map<array<int,3>, int> dp4;

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];
    if (dp4.count({i, sm, sm2})) 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)));
    return dp4[{i, sm, sm2}] = min(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) {
        // memset(dp4, -1, sizeof dp4);
        cout << rec4(0,0,0) << endl;
        return 0;
    }
}


/*

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

# 결과 실행 시간 메모리 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 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

# 결과 실행 시간 메모리 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 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 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

# 결과 실행 시간 메모리 Grader output
1 Correct 86 ms 107056 KB Output is correct
2 Correct 65 ms 106952 KB Output is correct
3 Correct 110 ms 107060 KB Output is correct
4 Correct 193 ms 107000 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 67 ms 107052 KB Output is correct

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 4784 KB Output is correct
2 Correct 671 ms 37476 KB Output is correct
3 Correct 12 ms 1492 KB Output is correct
4 Correct 11 ms 1376 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
0 / 28.0

# 결과 실행 시간 메모리 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 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 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 86 ms 107056 KB Output is correct
15 Correct 65 ms 106952 KB Output is correct
16 Correct 110 ms 107060 KB Output is correct
17 Correct 193 ms 107000 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 67 ms 107052 KB Output is correct
20 Correct 41 ms 4784 KB Output is correct
21 Correct 671 ms 37476 KB Output is correct
22 Correct 12 ms 1492 KB Output is correct
23 Correct 11 ms 1376 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Incorrect 1 ms 212 KB Output isn't correct
26 Halted 0 ms 0 KB -