Submission #536044

#	Time	Username	Problem	Language	Result	Execution time	Memory
536044		ctd6969	Bank (IZhO14_bank)	C++17	100 / 100	123 ms	8540 KiB

bank

#pragma GCC optimize ("Ofast")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")

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

typedef long long ll;
typedef long double db;

const ll mod = 1e9 + 7; // 500057 , 1000037 ,10000931 , 90903649 , 998244353, 109000057 , 1090000039
const ll inf = 1e18;

using pl = pair<ll,ll>;
using pi = pair<int,int>;
using vi = vector<int>; 
using vl = vector<ll>; 
using vpi = vector<pair<int,int>>;
using vpl = vector<pair<ll,ll>>;


#define mp make_pair
#define f first
#define s second

#define foru(i,a,b) for(int i = a ; i <= b;i++)
#define ford(i,a,b) for(int i = a ; i >= b;i--)

#define psh push
#define em emplace
#define eb emplace_back
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define debug(x) cout << x <<" ";



// #define LOCAL 1

void process(){
	int n , m;
	cin >> n >> m;
	ll a[n] , b[m];

	foru(i,0,n-1) cin >> a[i];
	foru(i,0,m-1) cin >> b[i];
	
	vi cover( (1<<m) , -1 );
	vi left( (1<<m) , -1 );

	bool ans = 0;
	cover[0] = 0;
	left[0] = 0;
	foru(i,0, (1<<m) - 1){
		foru(j,0,m-1){
			if( !((i>>j)&1) ) continue;

			int newmask = i^(1<<j);

			if(cover[newmask] == -1) continue;
			
			if( left[newmask] + b[j] < a[cover[newmask]] ){
				cover[i] = cover[newmask] ;
				left[i] = left[newmask] + b[j];
			} 
			else if( left[newmask] + b[j] == a[cover[newmask]] ) {
				cover[i] = cover[newmask] + 1;
				left[i] = 0;
			}
		}
		if( cover[i] == n ) {
			ans = 1;
			break;
		}
	}

	if(ans) cout << "YES" << '\n';
	else cout << "NO" << '\n';
}	


int main(void){

	#ifdef LOCAL
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		auto start_time = chrono::high_resolution_clock::now();
	#endif 

	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	
	process();

	#ifdef LOCAL
		auto end_time = chrono::high_resolution_clock::now();
		double duration = chrono::duration_cast<chrono::milliseconds>(end_time - start_time).count();
		cout << "\n[ " << duration << " ms ]\n";
	#endif

}

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