Submission #565529

#	Time	Username	Problem	Language	Result	Execution time	Memory
565529		gg123_pe	Bank (IZhO14_bank)	C++14	52 / 100	1084 ms	6656 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], vis[1<<20]; 
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,1,1<<m){
            bool fe = 1; 
            f(k,0,m) if(j&(1<<k) and on[j^(1<<k)][1]) fe = 0;

            if(!fe) continue; 

            for(int k = j; k > 0; k = (k-1)&j){
                if(on[k][2] and on[j^k][0]){
                    on[j][1] = 1;  
                    break; 
                }
            }
        }
        f(j,0,1<<m) vis[j] = 0; 

        f(j,0,1<<m){
            if(!on[j][1] or vis[j]) continue; 
            for(int k = j; k < 1<<m; k = (k+1)|j){
                if(vis[k]) break; 
                vis[k] = 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