제출 #1178236

#제출 시각아이디문제언어결과실행 시간메모리
1178236mrnachox은행 (IZhO14_bank)C++20
100 / 100
124 ms4520 KiB
#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;
    }

}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...