제출 #1164278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1164278		aram.hosna	Bank (IZhO14_bank)	C++20	0 / 100	1 ms	840 KiB

bank

/*in the name of god*/
#include <bits/stdc++.h>


using namespace std;

typedef long long ll ;
typedef long double ld ;
typedef pair<ll , ll > pii ;
typedef pair<ll , pii > pip ;

#define S   second
#define F   first
#define pb   push_back
#define ms(x , y)   memset(x , y , sizeof(x))
#define all(x)   x.begin() , x.end()
#define set_dec(x)	  cout << fixed << setprecision(x);
#define Mp(x , y)   make_pair(x , y)

const int N = 5e5+100 ;

ll a[22] , b[22]  , s[(1<<20)+1] , n , m, ps[22];
bool  dp[(1<<20)+1][21] ;
ll cac(int x){
    ll res = 0 ;
    for(int i = 0 ; i < m ; i++){
        if(x&i)res+=b[i];
    }
    return res ;
}
void solve(){
    cin >> n >> m ;
    for(int i = 1 ;i<=n ; i++){cin >> a[i]; ps[i] = ps[i-1]+a[i];}
    for(int j = 0 ; j < m; j++){cin >> b[j] ; }

    for(int mask = 0 ; mask < (1<<m) ; mask++){
        s[mask] = cac(mask);
        dp[mask][0] = 1 ;
    }


    for(ll mask = 0 ; mask < (1<<m) ; mask++){
        for(int i = 0 ; i <= n ; i++){
                if(dp[mask][i] == 0)continue ;
               // cout << mask << ' ' << i << endl;
            for(int j = 0 ; j < m ; j++){
                if(mask&j == 0){
                    if(s[mask^j] == ps[i+1])dp[mask^j][i+1] = 1 ;
                    else dp[mask^j][i] = 1 ;
                }
            }
        }
    }
    if(dp[(1<<m)-1][n-1])cout << "YES" << endl;
    else cout << "NO" << endl;
}


int main(){
    cin.tie(0)->sync_with_stdio(0) ;

    int tt=1 ;
   // cin >> tt ;
    while(tt--)solve();

    return 0 ;
}

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