Submission #567483

#	Time	Username	Problem	Language	Result	Execution time	Memory
567483		gg123_pe	Bank (IZhO14_bank)	C++14	100 / 100	266 ms	10444 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], dp[1<<20], sum[1<<20]; 
bool vis[1<<20]; 
set <int> s; 

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

    f(i,1,n+1) {
        cin >> a[i], a[i] += a[i-1]; 
        s.insert(a[i]); 
    }

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

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

    queue <int> q;
    q.push(0); 

    while(!q.empty()){
        int x = q.front(); q.pop(); 

        f(j,0,m){
            if(x&(1<<j)) continue; 

            int val = b[j+1] + sum[x], y = (1<<j) + x;

            if(s.count(val)) dp[y] = max(dp[y], 1 + dp[x]);
            else dp[y] = max(dp[y], dp[x]); 

            if(!vis[y]){
                vis[y] = 1; 
                q.push(y); 
            }
        }
    }
    f(i,1,1<<m){
        if(dp[i] == n){
            cout << "YES\n"; 
            return 0; 
        }
    }
    cout << "NO\n"; 
    return 0;
}

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