제출 #1001630

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001630		vjudge1	은행 (IZhO14_bank)	C++14	100 / 100	76 ms	8664 KiB

bank

#include<bits/stdc++.h>
using namespace std;
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin >> n >> m;
    int a[n+1];
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    int b[m];
    for(int i=0;i<m;i++){
        cin >> b[i];
    }
    bool flag=false;
    vector<pair<int,int>> DP(1<<m);
    for(int i=0;i<(1<<m);i++){
        DP[i].first=-1,DP[i].second=-1;
    }
    DP[0]={1,a[1]};
    for(int mask=0;mask<(1<<m);mask++){
        if(DP[mask].first==-1){
            continue;
        }
        for(int i=0;i<m;i++){
            if(!(mask&(1<<i))&&b[i]<=DP[mask].second){
                DP[mask^(1<<i)]={DP[mask].first,DP[mask].second-b[i]};
                if(DP[mask^(1<<i)].second==0){
                    DP[mask^(1<<i)].first++;
                    if(DP[mask^(1<<i)].first==n+1){
                        flag=true;
                        goto Label;
                    }
                    DP[mask^(1<<i)].second=a[DP[mask].first+1];
                }
            }
        }
    }
    Label:    ;
    if(flag){
        cout << "YES";
    }
    else{
        cout << "NO";
    }
}

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