제출 #937661

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
937661		Teemka	은행 (IZhO14_bank)	C++17	100 / 100	92 ms	8780 KiB

bank

#include "bits/stdc++.h" 
#define F first
#define S second
#define ALL(a) a.begin() , a.end()

#ifndef ONLINE_JUDGE
#define OK  cout << __LINE__ << "| "<< "---------------------------OK-----------------------" << endl;
#define deb(x) cout << __LINE__ << "| "<< #x  << " = " << x << endl;
#else
#define OK  
#define deb(x) 
#endif
 
typedef long double ld;
typedef long long ll;
using namespace std ;
const ll N = 21 ;	
const ll INF = 1e9;
const ll mod = 1e9 + 7 ;
const double eps = 1e-9 ;
const int dx[]  = { 0 , 0 , 1 , -1, 1 , -1 , 1 , -1} , dy[] = {1 , -1 , 0 , 0 , 1 , 1, -1 , -1}  ;
int n , m, a[N] , b[N];
pair<int,int> dp[1 << N];
void test_solve(int test_index){
	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 msk = 1; msk < (1 << m); msk++){
		for(int j = 0; j < m;j++){
			if(msk & ( 1 << j)){
				int k = dp[msk ^ (1 << j)].F , sm = dp[msk ^ (1 << j)].S + b[j + 1];
				if(sm == a[k + 1]){
					sm = 0;
					k++;
				}
				if(dp[msk].F < k){
					dp[msk] = {k , sm};
				}
				else if(dp[msk].F == k){
					dp[msk] = {k , sm};
				}
			}
		}
		if(dp[msk].F == n){
			cout << "YES" << endl;
			return;
		}
	}
	cout << "NO" << endl;
}

signed main(){
	ios_base::sync_with_stdio(false) ;
    cin.tie(0) ;
    cout.tie(0); 
	int test = 1;
	//cin >> test ;
	for(int i = 1 ;  i <= test ; i++){
 //		cout << "Case " << i << ": " ; 
		test_solve(i) ;
	}
  	return 0;	
}        

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