제출 #1198354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1198354		KindaGoodGames	은행 (IZhO14_bank)	C++20	52 / 100	626 ms	327680 KiB

bank

#include<bits/stdc++.h>

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

using namespace std;


int main(){
    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<set<int>> left(p2);
    //vector<int> left(p2,sal[0]);
    dp[0] = 0;
    left[0].insert(sal[0]);
    
    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(auto u : left[k-cur]){
                    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] = {sal[dp[k]]};
                }else if(dp[k-cur] > dp[k]){
                    dp[k] = dp[k-cur];
                    left[k] = left[k-cur];
                    for(auto u : left[k-cur]){
                        if(u-val[i] >= 0) left[k].insert(u-val[i]);
                    }
                }else if(dp[k-cur] == dp[k]){
                    for(auto u : left[k-cur]){
                        if(u-val[i] >= 0) left[k].insert(u-val[i]);
                    }
                }
            }
        }
    }

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

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