Submission #1182062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182062		fadak-14	Bank (IZhO14_bank)	C++20	71 / 100	1098 ms	130592 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;
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].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 ;
}
    
    

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