제출 #565514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
565514		gg123_pe	은행 (IZhO14_bank)	C++14	52 / 100	1090 ms	6712 KiB

bank

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

typedef long long ll; 
typedef pair<ll,ll> ii; 
#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

#define ff first 
#define ss second 

const int N = 1005; 
const ll inf = 1e17 + 100; 


int n, m, a[22], b[22]; 
bool on[1<<20][3]; 
vector <int> adj[N]; 

int main(){
    cin >> n >> m; 

    f(i,1,n+1) cin >> a[i]; 
    f(i,1,m+1) cin >> b[i]; 

    f(i,1,1<<m){
        int x = 0; 
        f(j,0,m) if(i&(1<<j)) x += b[j+1];

        if(x < N) adj[x].push_back(i);  
    }

    on[0][0] = 1; 

    f(i,1,n+1){
        for(int x: adj[a[i]]) on[x][2] = 1; 
         
        f(j,0,1<<m){
            for(int k = j; k > 0; k = (k-1)&j){
                if(on[k][2] and on[j^k][0]){
                    on[j][1] = 1;  
                    break; 
                }
            }
        }
        fa(j,(1<<m)-1,0){
            if(!on[j][1]) continue; 
            for(int k = j; k < 1<<m; k = (k+1)|j){
                on[k][1] = 1; 
            }
        }
        f(j,0,1<<m) 
            on[j][0] = on[j][1], on[j][1] = 0;
        
        for(int x: adj[a[i]]) on[x][2] = 0; 
    }
    cout << (on[(1<<m)-1][0] ? "YES\n" : "NO\n"); 
    return 0; 
}

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