Submission #468483

#	Time	Username	Problem	Language	Result	Execution time	Memory
468483		Shin	Bank (IZhO14_bank)	C++14	100 / 100	130 ms	8512 KiB

bank

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "file"
#define all(x) x.begin(), x.end()
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)

using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;

typedef long long ll;
typedef long double ld;
template <class X, class Y> bool minimize(X &a, Y b) {
    if (a > b) return a = b, true;
    return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
    if (a < b) return a = b, true;
    return false;
}

int n, m;
int bank[22];
int salary[22];
int dp[1 << 20];
int remain[1 << 20];

void solve(void) {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) cin >> salary[i];
    for (int i = 0; i < m; i ++) cin >> bank[i];

    memset(dp, -1, sizeof dp);
    dp[0] = 0;

    for (int mask = 0; mask < 1 << m; mask ++) {
        for (int i = 0; i < m ; i ++) if (BIT(mask, i)) {
            int nmask = mask ^ MASK(i);
            if (dp[nmask] < 0) continue;

            if (remain[nmask] + bank[i] < salary[dp[nmask]]) {
                dp[mask] = dp[nmask];
                remain[mask] = remain[nmask] + bank[i];
            } else
            if (remain[nmask] + bank[i] == salary[dp[nmask]]) {
                dp[mask] = dp[nmask] + 1;
                remain[mask] = 0;
            }
            if (dp[mask] == n) 
                return void (cout << "YES");
        }
    }
    cout <<"NO";
}

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

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