Submission #704046

#TimeUsernameProblemLanguageResultExecution timeMemory
704046vjudge1Bank (IZhO14_bank)C++14
0 / 100
2 ms468 KiB
// Problem: Elevator Rides

// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")

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

#define ff first
#define ss second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ones(x) __builtin_popcount(x)
#define remove(v)  v.erase(unique(all(v)), v.end())
#define rep(i, a, b) for(int i = a; i <= b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)

#ifdef local
#include "C:\debug.h"
#else
#define dbg(x...) 42
#endif
#define int long long

const int N = 2e6 + 2 ;
const int MOD = 1e9 + 7 ;
const int P = 1007 ;

void solve(){
    vector<pair<int,int>> v ;
    int n , m ;
    cin >> n >> m ;
    int a[n + 1] , b[m + 1] ;
    rep(i , 1 , n) cin >> a[i] ;
    set<int> w(a + 1 , a + 1 + n) ;
    rep(i , 1 , m) cin >> b[i] ;
    rep(i , 0 , (1 << m) - 1) {
        int cur = 0 ;
        rep(mask , 0 , m - 1) {
            if((i >> mask & 1)) {
                cur += b[mask + 1] ;
            }
        }
        if(w.count(cur)) {
            v.pb({cur , i}) ;
        }
    }
    sort(a + 1 , a + 1 + n) ;
    int sz = sz(v) ;
    assert(sz <= 20) ;
    rep(i , 0 , (1 << sz) - 1) {
        if(ones(i) != n) continue ;
        vector<int> e ; int cur = 0 ;  bool ok = 1 ;
        rep(mask , 0 , sz - 1) {
            if((i >> mask & 1)) {
                int t[31] = {0} ;
                rep(u , 0 , 30) {
                    if(cur >> u & 1) t[u]++ ;
                }
                rep(u , 0 , 30) {
                    if(v[mask].second >> u & 1) {
                        if(t[u]) {
                            ok = 0 ;
                            break ;
                        }
                        t[u]++ ;
                    }
                }
                if(!ok) break ;
                cur ^= v[mask].second ;
                e.pb(v[mask].first) ;
            }
        }
        if(!ok) continue ;
        sort(all(e)) ;
        rep(f , 0 , n - 1) {
            if(e[f] != a[f + 1]) {
                ok = 0 ;
                break ;
            }
        }
        if(!ok) continue ;
        cout << "YES" ;
        exit(0) ;
    }
    cout << "NO";
}

signed main () {
	// ios::sync_with_stdio(false) ;
	// cin.tie(0) ;
	int test = 1 ;
	// cin >> test ; 
	for(int i = 1 ; i <= test ; i++) {
		solve() ;
	}
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...