Submission #1245569

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245569		annn	Bank (IZhO14_bank)	C++20	100 / 100	105 ms	16852 KiB

bank

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

#define int long long
#define endl "\n"
#define pb push_back
#define ff first
#define ss second
#define ii pair<int, int>
#define vi vector<int>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define mii map<int, int>
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define _READ(name) freopen(name, "r", stdin)
#define _WRITE(name) freopen(name, "w", stdout)
const int INF = 4e18;
const int MOD = 1e9 + 7;

int n, m; const int mx = 20;
int a[mx],b[mx];
int dp[(1<<mx)];
int rem[(1<<mx)];
void Prepare() {
    cin >> n >> m;
    rep(i, 0, n-1) cin >> a[i];
    rep(i, 0, m-1) cin >> b[i];
}

void COOOOK() {
	memset(dp, -1, sizeof(dp));
	memset(rem, -1, sizeof(rem));
	dp[0] = 0;
	rem[0] = 0;
	int Max = (1<<m);
	
	for (int mask = 1; mask < Max; mask++) {
		for (int i = 0; i < m; i++) {
			if (!(mask>>i & 1)) continue;
			int pmask = mask^(1<<i);
			int bank = b[i];
			
			if (dp[pmask] == -1) continue;
			
			int got = rem[pmask] + bank;
			int salary = a[dp[pmask]];			
			
			if (got < salary) {
				dp[mask] = dp[pmask];
				rem[mask] = got;
			} else if (got == salary) {
				dp[mask] = dp[pmask]+1;
				rem[mask] = 0;
			}
		}
		if (dp[mask] == n) {
			cout << "YES"; return;
		}
	}
	cout << "NO";
}

void Eat() {
	
}

void Wash() {

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int TEST = 1;
    // cin >> TEST;
    while (TEST--) {
        Prepare();
        COOOOK();
        Eat();
        Wash();
    }

    return 0;

}

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