제출 #689971

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
689971		balthazar	은행 (IZhO14_bank)	C++14	0 / 100	2 ms	340 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];
    }
    
    pair<int, int> dp[1<<b];
    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(rest + bv[i]>av[valide+1])rest =bv[i];
                if(rest + bv[i]==av[valide+1]){
                valide+=1;
                rest=0;
                }
                if(rest+bv[i]<av[valide+1]){
                    rest+=bv[i];
                }
                
                dp[s]=max(dp[s], make_pair(valide, rest));
                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