제출 #1278110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278110		baktrr	은행 (IZhO14_bank)	C++20	71 / 100	1112 ms	235696 KiB

bank

/**
  III     U   U  N   N  DDDD   EEEEE  RRRR   SSSS  TTTTT  AAAAA  N   N  DDDD      I  TTTTT     N   N   OOO   W   W
   I      U   U  NN  N  D   D  E      R   R  S       T    A   A  NN  N  D   D     I    T       NN  N  O   O  W   W
   I      U   U  N N N  D   D  EEEE   RRRR   SSSS    T    AAAAA  N N N  D   D     I    T       N N N  O   O  W W W
   I      U   U  N  NN  D   D  E      R  R      S    T    A   A  N  NN  D   D     I    T       N  NN  O   O  WW WW
  III     UUUUU  N   N  DDDD   EEEEE  R   R  SSSS    T    A   A  N   N  DDDD      I    T       N   N   OOO   W   W
**/

//18.09.25
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;
// using namespace __gnu_pbds;
 
#define ent '\n'
#define F first
#define S second
#define in insert
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define sz(w) w.size()
#define int long long
#define pii pair <int, int>
#define all(w) w.begin(), w.end()
#define rall(w) w.rbegin(), w.rend()
#define BakTR ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
const int MOD = 998244353, N = 1e5 + 7 , inf = 1e9 + 7, INF = 2e18, LOG = 20 , mod = 1e9 + 7 , block = 300 ;
 
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// template <typename T>
// using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

vector <int> cnt[N] ;
int us[20][N] ;
int a[N] , b[N] , n , m ;

void rec(int i , int x) {
    if(us[i][x]) return ;
    us[i][x] = 1 ;
    if(i == n) {
        cout << yes ;
        exit(0) ;
    }
    for(int it : cnt[a[i]]) {
        if(x + it == (x | it)) {
            rec(i + 1 , x + it) ;
        }
    }
}

void accepted() {
    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 mask = 1 ; mask < (1 << m) ; mask++) {
        int sum = 0 ;
        for(int i = 0 ; i < m ; i++) {
            if((mask >> i) & 1) {
                sum += b[i] ;
            }
            cnt[sum].pb(mask) ;
        }
    }
    rec(0 , 0) ;
    cout << no ;
}

signed main() {
    BakTR
    //PLS NeverGiveUp
 
    // freopen("sum2.in", "r", stdin) ;
    // freopen("sum2.out", "w", stdout) ;

    int T = 1 ;
    // cin >> T ;
    while (T--) {
        accepted() ;
        // cout << ent ;
    }
}

/**
baktr
const int N = 1e5 + 1 ;
int n, m, a[21], b[21] ;
bool us[21][(1 << 20)] ;
vector< int >mp[N] ;

void rec( int i, int sum )
{
    if( us[i][sum] )
        return;
    us[i][sum] = true;
    if( i == n )
    {
        cout <<"YES\n";
        exit(0);
    }
    for( int x: mp[a[i]] )
        if( sum + x == (sum | x) )
            rec(i + 1, sum + x);
}

void solve()
{
    cin >>n >>m;
    for( int i = 0; i < n; ++i )
        cin >>a[i];
    for( int j = 0; j < m; ++j )
        cin >>b[j];
    for( int mask = 0; mask < (1 << m); ++mask )
    {
        int sum = 0;
        for( int i = 0; i < m; ++i )
            if( (1 << i) & mask )
                sum += b[i];
        mp[sum].pb( mask );
    }
    rec(0, 0);
    cout <<"NO\n";
**/

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