//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n ,m ;
vector<vector<int>> dp ;
bool sv(int c , int i , vector <int> &arr, vector<vector<int>> &sm) {
if(i == n) return true ;
if(dp[c][i] != -1) return dp[c][i] == 1 ;
for(int &j : sm[arr[i]]) {
if(j & c) continue ;
if(sv(j | c , i +1 , arr , sm)) return dp[c][i] = 1 ;
}
return dp[c][i] == 0 ;
}
signed main() {
cin.tie(0)->sync_with_stdio(0);
ios::sync_with_stdio(0);
cin.tie(0) ; cout.tie(0);
cin >> n >> m ;
vector <int> arr(n) ;
vector<int> b (m) ;
int mx = 0 ; for(int &i : arr) cin >> i ;
for(int &i : b) {cin >> i ; mx += i;}
vector<vector<int>> sm (mx +1) ;
dp.resize((1 << m) + 1 , vector<int> (n + 1 , -1)) ;
int t = 1 << m ;
for(int i = 0 ; i < t ;i++) {
int c= 0 ;
for(int j = 0 ; j < m ; j++) if(i & (1 << j)) c += b[j] ;
if(c >mx) continue ;
sm[c].push_back(i) ;
}
for(int &i :arr) {
if(i > mx) {cout << "NO\n" ; return 0;}
if(sm[i].empty()) {cout << "NO\n" ; return 0 ;}
}
if(sv(0 , 0 , arr, sm)) {cout << "YES\n" ;} else cout << "NO\n";
return 0 ;
}
# | 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... |