Submission #1056430

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056430		vjudge1	Bank (IZhO14_bank)	C++17	100 / 100	702 ms	12624 KiB

bank

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define fi first
#define se second

const int N=1e3+9;
const int M=20;
int n,m,a[N],b[N];
vector<int> sum[N];
 main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    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 i=0;i<(1<<m);i++){
        int curr=0;
        for(int j=0;j<m;j++) {
            if(i&(1<<j)) curr+=b[j];
        }
        if(curr<N) sum[curr].push_back(i);
    }
    vector<bool> dp(1 << m), prev(1 << m);
    dp[0]=true;
    for(int i=0;i<n;i++){
        swap(dp,prev);
        for(int mask=0;mask<(1<<m);mask++){
            dp[mask]=0;
        }
        for(auto mask:sum[a[i]]) {
            for(int mask1=mask;mask1<(1<<m);++mask1|=mask) {
                if(prev[mask1^mask]) {
                    dp[mask1] = true;
                }
            }
        }
    }
    bool res=0;
    for(int i=0;i<(1 << m);i++) {
        if(dp[i]){
            res = 1;
        }
    }
    if(res==1) cout<<"YES";
    else       cout<<"NO";

}

Compilation message (stderr)

bank.cpp:12:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 |  main()
      |  ^~~~

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