제출 #1198359

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198359		KindaGoodGames	Bank (IZhO14_bank)	C++20	0 / 100	74 ms	2376 KiB

bank

#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;
    
    for(int k = 1; k < p2; k++){
        for(int i = 0; i < m; i++){
            if(dp[k] >= n) break;
            int cur = (1 << i);
            if(k & cur){
                bool pos = false;
                 
                for(int u = 1; 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];
                    for(int u = 1; u <= 1000; u = left[k-cur]._Find_next(u)){
                        if(u-val[i] >= 0) left[k][u-val[i]] = true;
                    }
                }else if(dp[k-cur] == dp[k]){
                    for(int u = 1; u <= 1000; u = left[k-cur]._Find_next(u)){
                        if(u-val[i] >= 0) left[k][u-val[i]] = true;
                    }
                }
            }
        }
    }

    if(dp[p2-1] == n){
        cout << "YES\n";
    }else{
        cout << "NO\n";
    }
}

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