제출 #1196413

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1196413		easterp	Bank (IZhO14_bank)	C++20	71 / 100	1093 ms	2440 KiB

bank

/// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
/// Training ICPC 2024

#include<bits/stdc++.h>

/// #pragma GCC optimize("O3,unroll-loops")
/// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#define fi first
#define se second
#define TASK "bank"
#define pb push_back
#define EL cout << endl
#define Ti20_ntson int main()
#define in(x) cout << x << endl
#define all(x) (x).begin(),(x).end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> vii;
typedef unsigned long long ull;
typedef vector<vector<int>> vvi;
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }

const int N = 5e5 + 5;
const int oo = INT_MAX;
const int mod = 1e9 + 7;
const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, a[N], m, b[N];
bool dp[22][(1 << 20) + 5];


inline void Read_Input() {
    cin >> n >> m;
    FOR(i, 1, n)
        cin >> a[i];
    FOR(i, 1, m)
        cin >> b[i];
}

inline void Solve() {
    dp[0][0] = true;

    for (int i = 0; i < n; i++)
        for (int j = 0; j < (1 << m); j++)

            if (dp[i][j] == true) {

                /// tra tien cho nguoi (i + 1)

                for (int msk = 0; msk < (1 << m); msk++)
                    if ((msk & j) == 0) {

                        int Sum = 0;
                        for (int k = 1; k <= m; k++)
                            if (getbit(msk, k - 1))
                                Sum += b[k];

                        if (Sum == a[i + 1])
                            dp[i + 1][j + msk] = true;
                    }
            }

    bool Ans = false;

    for (int msk = 0; msk < (1 << m); msk++)
        if (dp[n][msk] == true) Ans = true;

    if (Ans) cout << "YES";
    else cout << "NO";
}

Ti20_ntson {
//    freopen(TASK".inp","r",stdin);
//    freopen(TASK".out","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T -- ) {
        Read_Input();
        Solve();
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29