제출 #691895

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
691895		balthazar	은행 (IZhO14_bank)	C++14	0 / 100	2 ms	444 KiB

bank

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    int a;
    int b;
    cin>>a>>b;
    vector<int>av(a);
    vector<int>bv(b);
    for(int i=0;i<a;i++){
        cin>>av[i];
    }
    for(int i =0;i<b;i++){
        cin>>bv[i];
    }
    
    vector<pair<int, int>> dp(1<<b,{-1,0});
    dp[0]={0,0};
    for(int s=1;s<(1<<b);s++){
        for(int i = 0;i<b;i++){
            if(s>>i&1){
                auto prev = dp[s^(1<<i)];
                int valide = prev.first;
                int rest = prev.second;
                if(valide == -1)continue;
                if(rest + bv[i]==av[valide]){
                    dp[s].first=valide+1;
                    dp[s].second=0;
                }
                if(rest+bv[i]<av[valide] && dp[s].first <= valide){
                    
                    dp[s].first=valide;
                    dp[s].second=rest+bv[i];
                }
                
                
                if(dp[s].first == a){
                    cout<<"YES";
                    return 0;
                }
                
            }
        }
    }
    cout<<"N0";
    
}

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