Submission #1256010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256010		vuquangminh	Bank (IZhO14_bank)	C++17	100 / 100	338 ms	19528 KiB

bank

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


#define Task ""

#define ALL_MY_FELLAS() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define fx(x) fixed << setprecision(x) 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair
#define sz(x) (x).size()
#define len(x) (x).length()
#define endl "\n"
#define FOR(type, var, a, b, c) for (type var = (a); ((c) > 0 ? var <= (b) : var >= (b)); var += (c))
//#define int long long


typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;


const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;
const ll INF = 0x3f3f3f3f3f;
const int OO = 30000;


int n, m, a[25], b[25], dp[1 << 20];
vector<vector<ll>> s;


void solve() {
	cin >> n >> m;
	ll sum = 0;
	FOR(int, i, 0, n -1, 1) {cin >> a[i]; sum += a[i];}
	FOR(int, i, 0, m - 1, 1) cin >> b[i];
	
	s.assign(OO, {});
	
	int mx = 1 << m;
	FOR(int, mask, 0, mx - 1, 1) {
		ll total = 0;
		FOR(int, i, 0, m, 1) {
			if ((mask >> i) & 1) total += b[i];
		}
		s[total].pb(mask);
	}
	
	fill(dp + 1, dp + mx + 1, -1);
	dp[0] = 0;
	FOR(int, mask, 0, mx - 1, 1) {
		if (dp[mask] == -1) continue;
		ll total = 0;
		FOR(int, i, 0, m - 1, 1) {
			if ((mask >> i) & 1) total += b[i];
		}
		int id = dp[mask];
		if (id == n) continue;
		for (int emask : s[a[id]]) {
			if ((emask & mask) > 0) continue;
			ll nmask = emask | mask;
			dp[nmask] = max(dp[nmask], dp[mask] + 1);
		}
	}
	
	bool ok = false;
	FOR(int, mask, 0, mx - 1, 1) {
		if (dp[mask] == n) {
			ok = true;
			break;
		}
	}
	
	cout << (ok ? "YES" : "NO");
}


signed main() {
	if (fopen(Task".inp", "r")) {
		freopen(Task".inp", "r", stdin);
		freopen(Task".out", "w", stdout);
	}
	
    ALL_MY_FELLAS();
    solve();
    //cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << 's' << endl;
    
    return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:95:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 freopen(Task".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:96:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 freopen(Task".out", "w", stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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