Submission #1206426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206426		phanminhanh2162022	은행 (IZhO14_bank)	C++20	0 / 100	1 ms	580 KiB

bank

#include <bits/stdc++.h>
using namespace std ;

#define int long long
#define BIT(x , i) (((x) >> (i)) & 1)
#define MASK(i) (1ll << (i)) 
#define pb push_back
#define endl '\n'
#define LOG 19

const int INF = -100 ;

void process(void) {
    int n , m ; cin >> n >> m ;
    vector <int> a(n + 1) , b(m + 1) ;
    for(int i = 1 ; i <= n ; ++i) {
        cin >> a[i] ;
    }
    for(int i = 1 ; i <= m ; ++i) {
        cin >> b[i] ;
    }
    int fullMask = MASK(m) ;
    vector <int> dp(fullMask , INF) , sum(fullMask) ;
    sum[0] = dp[0] = 0 ;
    for(int i = 1 ; i <= m ; ++i) {
        sum[MASK(i - 1)] = b[i] ;
    }
    for(int mask = 0 ; mask < fullMask ; ++mask) {
        if(__builtin_popcount(mask) <= 1) continue ;
        int sub = mask & -mask ;
        sum[mask] = sum[sub] + sum[mask ^ sub] ;
    }
    vector <int> op[n + 1] ;
    for(int i = 1 ; i <= n ; ++i) {
        for(int mask = 0 ; mask < fullMask ; ++mask) {
            if(sum[mask] == a[i]) {
                op[i].pb(mask) ;
            }
        }
    }
    for(int mask = 0 ; mask < fullMask ; ++mask) {
        if(dp[mask] == INF) continue ;
        if(dp[mask] == n) break ;
        int nextPos = dp[mask] + 1 , need = a[nextPos] ;
        for(int sub : op[nextPos]) {
            if(sub & mask == 0) {
                dp[mask | sub] = max(dp[mask | sub] , dp[mask] + 1) ;
            }
        }
    }
    for(int mask = 0 ; mask < fullMask ; ++mask) {
        if(dp[mask] == n) {
            cout << "YES\n" ;
            return ;
        }
    }
    cout << "NO\n" ;
}

int32_t main(void) {
    ios_base :: sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cout.tie(nullptr) ;
    process() ;
    return 0 ;
} 

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