Submission #89347

#	Time	Username	Problem	Language	Result	Execution time	Memory
89347		abil	Bank (IZhO14_bank)	C++14	100 / 100	387 ms	118508 KiB

bank

/**
   Solution by Abil
**/
# include <bits/stdc++.h>

# define fr first
# define sc second
# define pb push_back
# define mk make_pair
# define sz(s) s.size()
# define all(s) s.begin(),s.end()
# define int long long

using namespace std;

const long long N = (1e6 + 10);
const long long mod = (1e9 + 7);
const long long inf = (1e9 + 7 + 1e9);

int a[N],b[N];
int n, m, used[21][(1 << 20) + 10];
vector<int > v[N];
void f(int y,int x){
    if(y > n){
      cout << "YES";
      exit(0);
    }
    if(used[y][x]){
      return;
    }
    used[y][x] = 1;
    for(auto i : v[y]){
      if((x & i) == 0){
        f(y + 1,(x ^ i));
      }
    }
}
main()
{
   ios_base::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   cin >> n >> m;
   for(int i = 1;i <= n; i++){
      cin >> a[i];
   }
   for(int i = 1;i <= m; i++){
    cin >> b[i];
   }
   for(int mask = 0;mask < (1 << m); mask++){
     int sum = 0;
     for(int i = 0;i < m; i++){
      if(mask & (1 << i)){
        sum += b[i + 1];
      }
     }
     for(int i = 1;i <= n; i++){
      if(a[i] == sum){
        v[i].pb(mask);
      }
     }
   }
   f(1,0);
   cout << "NO";
}

Compilation message (stderr)

bank.cpp:38:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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