Submission #1198385

#TimeUsernameProblemLanguageResultExecution timeMemory
1198385KindaGoodGamesBank (IZhO14_bank)C++20
100 / 100
152 ms16840 KiB
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2")
#include<bits/stdc++.h>

#define ll long long
#define int ll
#define pii pair<int,int>
#define tiii tuple<int,int,int>
//#define bs bitset<1001>

using namespace std;


int32_t main(){
    //bs nothing;
    int n,m;
    cin >> n >> m;
    vector<int> sal(n),val(m);

    for(int i = 0; i < n; i++){
        cin >> sal[i];
    }
    for(int i = 0; i < m; i++){
        cin >> val[i];
    } 

    int p2 = (1<<m);

    vector<int> dp(p2,-1);
    //vector<bs> left(p2);
    vector<int> left(p2,1e9);
    dp[0] = 0;
    left[0] =sal[0];
    bool early = false;
    
    for(int k = 1; k < p2; k++){
        if(early) break;
        for(int i = 0; i < m; i++){
            if(dp[k] >= n) {
                early = true;
                break;
            }
            int cur = (1 << i);
            if(k & cur){
                bool pos = left[k-cur] == val[i];
                  

                if(pos && dp[k-cur]+1 > dp[k]){
                    dp[k] = dp[k-cur]+1;
                    if(dp[k] >= n) break;
                    left[k] = sal[dp[k]]; 
                }else if(dp[k-cur] > dp[k]){
                    dp[k] = dp[k-cur];
                    left[k] = left[k-cur];
                    if(left[k-cur]-val[i] >= 0)left[k]-=val[i]; 
                }
                else if(dp[k-cur] == dp[k]){
                    if(left[k-cur]-val[i] >= 0)left[k] = min(left[k] ,left[k-cur]-val[i]); 
                }
            }
        }
    }

    if(dp[p2-1] == n ||early){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...