제출 #1182060

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1182060		fadak-14	은행 (IZhO14_bank)	C++20	71 / 100	1100 ms	130700 KiB

bank

//Wa of course, please give me ac !!! im begging u compiler-sama, have mercy on my poor code !
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define endl '\n'
#define eb emplace_back
#define em emplace
#define pb push_back
#define pf push_front
#define pp pop_back
#define fr first
#define sc second
#define sz size
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() {
    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].pb(i) ;
    }
    for(int &i :arr) {
        if(i > mx) {cout << "NO" << endl ; return 0;}
        if(sm[i].empty()) {cout << "NO" << endl ; return 0 ;} 

    }
    if(sv(0 , 0 , arr, sm)) {cout << "YES" << endl;} else cout << "NO" << endl;
    return 0 ;
}
    
    

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