제출 #1198365

#제출 시각아이디문제언어결과실행 시간메모리
1198365KindaGoodGames은행 (IZhO14_bank)C++20
52 / 100
1100 ms135856 KiB
#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>

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

using namespace std;


int 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,sal[0]);
    dp[0] = 0;
    left[0][sal[0]] = true;
    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 = false;
                 
                for(int u = 0; u <= 1000; u = left[k-cur]._Find_next(u)){
                    if(u == val[i]){
                        pos = true;
                        break;
                    }
                }

                if(pos && dp[k-cur]+1 > dp[k]){
                    dp[k] = dp[k-cur]+1;
                    if(dp[k] >= n) break;
                    left[k] = nothing;
                    left[k][sal[dp[k]]] = 1;
                }else if(dp[k-cur] > dp[k]){
                    dp[k] = dp[k-cur];
                    left[k] = left[k-cur];
                    left[k] |= (left[k-cur] >> val[i]); 
                }else if(dp[k-cur] == dp[k]){
                    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...