Submission #1178236

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178236		mrnachox	Bank (IZhO14_bank)	C++20	100 / 100	124 ms	4520 KiB

bank

#include<bits/stdc++.h>

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)
#define repx(i, a, b) for (int i = (int)a; i < (int)b; i++)

int n, m;
vector<int> b;
vector<int> cuts;
vector<int> DP;

bool valid_jump(int sum, int delta){
    if(sum >= cuts.back()) return false;
    int next_cut = *upper_bound(cuts.begin(), cuts.end(), sum);
    if(sum + delta > next_cut) return false;
    return true;
}

int f(int mask, int sum){
    if(DP[mask] != -1) return DP[mask];
    if(sum == cuts.back()) return DP[mask] = true;
    rep(i, m){
        if(mask & (1 << i)) continue;
        if(!valid_jump(sum, b[i])) continue;
        if(f(mask | (1 << i), sum + b[i]))
            return DP[mask] = true;
    }
    return DP[mask] = false;
}


int main(){

    cin >> n >> m;
    DP.resize(1 << m, -1);
    cuts.resize(n);
    b.resize(m);

    rep(i, n){
        cin >> cuts[i];
    }
    rep(i, n-1){
        cuts[i+1] += cuts[i];
    }
    rep(i, m){
        cin >> b[i];
    }

    if(f(0, 0)){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

}

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