#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |