Submission #672197

#	Time	Username	Problem	Language	Result	Execution time	Memory
672197		Cutebol	Bank (IZhO14_bank)	C++17	100 / 100	163 ms	61460 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;
 
//void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define Scaramouche ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define itn int
#define endl "\n"
#define ff first
#define ss second
   
const int N = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int inf = 1e12 ;

int n , m ;
bool vis[23][2000000] ;
vector <int> vec[2000000] ;
int a[23] , b[23] ;

void rec( int ind , int cur ){
	if ( ind == n + 1 ){
		cout << "YES" ;
		exit(0) ;
	}
	vis[ind][cur] = 1 ;
	for ( auto i : vec[ind] ){
		if ( (cur & i) == 0 && (!vis[ind+1][cur^i]) )
			rec ( ind + 1 , cur ^ i ) ;
	}
}

void solve(){
	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 i = 1 ; i < ( 1 << m ) ; i ++ ){
		int sum = 0 ;
		for ( int j = 0 ; j < m ; j ++ )
			if ( i & ( 1 << j ) ) sum += b[j+1] ;
		for ( int j = 1 ; j <= n ; j ++ ){
			if ( a[j] == sum ) vec[j].push_back(i) ;
		}
	}
	
	rec( 1 , 0 ) ;
	cout << "NO" ;	
}
 
signed main(){
//  fopn("talent") ;
//    Scaramouche ;
    int t = 1 ;
//      cin >> t ;
    while ( t -- ) solve() ; 
}

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