제출 #1086864

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086864		lhlephuocdao	은행 (IZhO14_bank)	C++14	100 / 100	105 ms	57784 KiB

bank

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

#include <bits/stdc++.h>
 
using namespace std;
 
const int Z = 20;
// int N, M, A[Z], B[Z];
vector<int> S[Z];
set<int> dp[1<<Z]; // dp[s] : states of subset S


#define MASK(k) (1LL << (k))
#define BIT(x, i) (((x) >> (i)) & 1)
const int MAX = 20;
 
int N, M;
int a[MAX + 10], b[MAX + 10], l[MASK(MAX) + 10], f[MASK(MAX) + 10];
 
void solve(){
    cin >> N >> M;
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    for(int i=0; i<M; i++){
        cin >> b[i];
    }
    memset(f, -1, sizeof f);
    f[0] = 0;
 
    for(int mask=0; mask < (1<<M); mask++)
        if(f[mask] != -1){
            for(int i=0; i < M; i++)
                if(!(mask & (1<<i))){
                    int x = b[i] + l[mask];
                    if(x < a[f[mask]]){
                        f[mask | (1<<i)] = f[mask];
                        l[mask | (1<<i)] = x;
                    }
                    else if(x == a[f[mask]]){
                        f[mask | (1<<i)] = f[mask] + 1;
                        l[mask | (1<<i)] = 0;
                    }
                    if(f[mask | (1<<i)] == N){
                        cout << "YES\n";
                        return;
                    }
                }
        }
 
    cout << "NO\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    solve();
/*
    cin >> N >> M;
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];
 
	for (int state = 1; state < (1 << M); state++) {
		int sum = 0;
		for (int i = 0; i < M; i++) if (state & (1 << i)) sum += B[i];
		for (int i = 0; i < N; i++) if (sum == A[i]) {
            S[i].push_back(state);
            dp[1<<i].insert(state);
        }
	}
 
    //dp[0] = empty
    for (int s = 1; s < (1<<N); s++)
    {
        for (int i = 0; i < N; i++)
        {
            if (!(s & (1<<i)) || dp[s^(1<<i)].empty()) continue;

            for (auto cur_state : S[i])
                for (auto prev_state : dp[s^(1<<i)])
                {
                    if (cur_state & prev_state) continue;
                    dp[s].insert(cur_state | prev_state);
                }
        }

        if (!dp[(1<<N)-1].empty()) {  // Early exit if found
            cout << "YES";
            return 0;
        }
    }

    cout << "NO";
*/
 
	return 0;
}

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