제출 #1206419

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206419		phanminhanh2162022	은행 (IZhO14_bank)	C++20	71 / 100	1096 ms	16732 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] ;
    }
    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] ;
        // duyet qua cas subMask sao cho (mask & subMask) == 0 
        int revMask = mask ^ (fullMask - 1) ;
        for(int sub = revMask ; sub >= 0 ; sub = (sub - 1) & revMask) {
            if(sum[sub] == need) {
                dp[mask | sub] = max(dp[mask | sub] , dp[mask] + 1) ;
            }
            if(sub == 0) break ;
        }
    }
    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: 19 / 19
• Subtask 2: 25 / 25
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29