제출 #1098183

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1098183		nmts	은행 (IZhO14_bank)	C++17	100 / 100	82 ms	8796 KiB

bank

#include <bits/stdc++.h>

#define file(name) freopen(name".inp" , "r" , stdin),freopen(name".out" , "w" , stdout);
#define faster    ios_base :: sync_with_stdio(false) , cin.tie(0) , cout.tie(0) 
#define pii pair < int , int >
#define fi first
#define se second
#define endl '\n'    
#define ll long long
const int maxn = 1e6 + 6;
const int mod= 1e9 + 7;
const ll INFLL= 3e18 + 5;
const int INF = 1e9 + 5 ;
const int LOG = 20 ;
const int block_sz = 316;


template<class T> bool minimize(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool maximize(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

using namespace std;

int n , m;

int sal[maxn];
int tenge[maxn];

pii dp[(1 << 20) + 6];

void solve()
{

	cin >> n >> m;

	for (int i = 0 ; i < n ; ++i) cin >> sal[i];

	for (int i = 0 ; i < m ; ++i) cin >> tenge[i];

	for (int Mask = 0 ; Mask < (1 << m) ; ++Mask) dp[Mask] = make_pair(-1 , -1);

	dp[0] = make_pair(0 , 0);

	for (int Mask = 1 ; Mask < (1 << m) ; ++Mask)
		for (int i = 0 ; i < m ; ++i)
			if (Mask & (1 << i))
				{
					
					if (dp[Mask - (1 << i)].fi == -1) continue;

					int val = sal[dp[Mask - (1 << i)].fi];

					int cur = dp[Mask - (1 << i)].se;

					if (cur + tenge[i] == val)
						{
							dp[Mask].fi = dp[Mask - (1 << i)].fi + 1;
							dp[Mask].se = 0;
						}
					else 
					if (cur + tenge[i] < val)
						{
							dp[Mask].fi = dp[Mask - (1 << i)].fi;
							dp[Mask].se = cur + tenge[i];
						}

					
					if (dp[Mask].fi == n)
						{
							cout << "YES" << endl;
							return;
						}

				}
	cout << "NO" << endl;


}


int32_t main()
{
	faster;
	// file("txt");
	// int t ; cin >> t ; while (t--)
	solve();
	return 0;
}

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