제출 #861298

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
861298		RashedKhalil	은행 (IZhO14_bank)	C++17	100 / 100	106 ms	8892 KiB

bank

#include <bits/stdc++.h>

using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;	// tosnu [nu_s]
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
// Usage: insert, find, erase same as set;
// order_of_key(k): Number of items strictly smaller than k
// find_by_order(k): k-th element in a set (counting from zero)

#define ll long long 
#define sz(x) int(x.size())
#define Rashed_To_Get_Accepted ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
const int MOD =1e9+7;  // 1e9+7 ,998244353;
int cbit(int x){return __builtin_popcount(x);}
ll gcd(ll a, ll b) {if (b > a) {return gcd(b, a);} if (b == 0) {return a;} return gcd(b, a % b);}

// iota(a.begin() , a.end() , x) , x here means start int

// sort(ord.begin(), ord.end(), [&cnt](int x, int y){
	// return cnt[x] > cnt[y];
// });
// stoi(str) to convert string to int  
// dp?, graph?, bs on answer?, stupid observation? parent query binary lifting?

int dx[] = {1,  -1  ,0 , 0 , -1 , -1 , 1 , 1};
int dy[] = {0 , 0 , -1 , 1 , 1 , -1 , 1 , -1};

const int N = 20 , LOG = 18;

int dp[1 << N] , Taken[1 << N];
int people[N] , bkn[N];
void solve()
{
	int n , m ; cin >> n >> m;
	for(int i =0 ;i < n ;i++)cin >> people[i];
	for(int i =0 ;i < m ;i++)cin>> bkn[i];
	
	memset(dp , -1 , sizeof dp);
	dp[0] = 0;
	Taken[0] = 0;
	
	for(int mask =1 ; mask <(1 << m) ; mask++){
		
		for(int b =0 ; b < m ; b++){
			if((mask &(1 << b))){
				int pmask = mask ^(1 << b);
				if(dp[pmask] == -1)continue;
				int new_val = Taken[pmask] + bkn[b];
				
				if(new_val < people[dp[pmask]]){
					dp[mask] = dp[pmask];
					Taken[mask] = new_val;
				}
				
				
				else if (new_val == people[dp[pmask]]){
					dp[mask] = dp[pmask] + 1;
					Taken[mask] = 0;
				}
			}
		}
		
		if(dp[mask] == n){
			cout <<"YES\n";
			return;
		}
	}
	
	cout <<"NO\n";
}


int main(){
	
	Rashed_To_Get_Accepted
	int tc;
	tc = 1;
	// cout << fixed << setprecision(6);
	// cin >> tc;
	while(tc--){
		solve();
	}
	return 0;
	
}	

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