Submission #1128326

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128326		imposterx	Bank (IZhO14_bank)	C++20	100 / 100	262 ms	82516 KiB

bank

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

void fast() {
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    // freopen("bank.in", "r", stdin);
    // freopen("bank.out", "w", stdout);
}


#define sz(x) (int)x.size()

/*
 * 8 10 15 12
 * mask = 01111, j = 2
 * curs = 3
 * curs = 8 - pre[j - 1]
 * curs = 5
 * curs = 10 - pre[j - 1]
 */

int dp[20][1ll << 20], a[20], b[20], n, m, p[21];

int mem(int mask, int j) {
    if (j == n){
        return 1;
    }
    if (__builtin_popcount(mask) == m)return 0;
    int rem = m - __builtin_popcount(mask);
    //if (rem < n - j)return 0;
    int &ret = dp[j][mask];
    if (~ret)return ret;
    ret = 0;
    int curs = 0;
    for(int i = 0; i < m; i++) {
        if (mask >> i & 1){
            curs += b[i];
        }
    }
    curs -= p[j];
    for(int i = 0; i < m; i++) {
        if (mask >> i & 1)continue;
        if (curs + b[i] < a[j]) {
            ret |= mem(mask | (1ll << i), j);
        }
        else if (curs + b[i] == a[j]) {
            ret |= mem(mask | (1ll << i), j + 1);
        }
    }
    return ret;
}

void burn(){
    cin >> n >> m;
    for(int i = 0; i < n; i++)cin >> a[i], p[i + 1] = a[i] + p[i];
    for(int j = 0; j < m; j++)cin >> b[j];
    memset(dp, -1, sizeof dp);
    cout << (mem(0, 0)?"YES\n":"NO\n");
}

int32_t main() {
    fast();
    int t = 1;
    //cin >> t;
    while(t--) {
        burn();
    }
}

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