Submission #928223

#	Time	Username	Problem	Language	Result	Execution time	Memory
928223		vjudge1	은행 (IZhO14_bank)	C++17	100 / 100	100 ms	8788 KiB

bank

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
#define in insert
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)x.size()
#define deb(x) cout << #x << " = " << x << '\n';
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)
using namespace std;

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

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;

int n, m, a[25], b[25], dp[1 << 20], rem[1 << 20];

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];
	}
	memset(dp, -1, sizeof dp);
	dp[0] = 0;
	rem[0] = 0;
	for(int mask = 1; mask < (1 << m); mask++) {
		for(int last = 1; last <= m; last++) {
			if((mask >> (last - 1)) & 1) {
				int prev = (mask ^ (1 << (last - 1)));
				if(dp[prev] == -1) continue;
				if(rem[prev] + b[last] == a[dp[prev] + 1] && dp[mask] < dp[prev] + 1) {
					dp[mask] = dp[prev] + 1;
					rem[mask] = 0;
				}
				else if(rem[prev] + b[last] < a[dp[prev] + 1] && dp[mask] < dp[prev]) {
					dp[mask] = dp[prev];
					rem[mask] = rem[prev] + b[last];
				}
			}
		}
		if(dp[mask] == n) {
			cout << "YES\n";
			return;
		}
	}
	cout << "NO\n";
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int TT = 1;
	// cin >> TT;
	while(TT--) {
		solve();
	}
	return 0;
}

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