제출 #1147410

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147410		AlgorithmWarrior	은행 (IZhO14_bank)	C++20	0 / 100	0 ms	324 KiB

bank

#include <bits/stdc++.h>

using namespace std;

ifstream fin("bank.in");
ofstream fout("bank.out");

int n,m;
int a[23];
int b[23];

void read(){
    fin>>n>>m;
    int i;
    for(i=0;i<n;++i)
        fin>>a[i];
    for(i=0;i<m;++i)
        fin>>b[i];
}

struct plata{
    int ind,val;
    bool operator != (plata ot){
        return (ind!=ot.ind || val!=ot.val);
    }
    bool operator == (plata ot){
        return (ind==ot.ind && val==ot.val);
    }
}dp[1050000];

bool get_dp(){
    dp[0]={0,a[0]};
    plata imp={-1,0};
    int i,bit;
    for(i=1;i<(1<<m);++i){
        dp[i]=imp;
        for(bit=0;bit<m;++bit)
            if(i&(1<<bit)){
                int vechi=i^(1<<bit);
                int ind=dp[vechi].ind;
                int new_val=dp[vechi].val-b[bit];
                if(dp[vechi]!=imp && new_val>=0){
                    if(new_val){
                        dp[i].ind=ind;
                        dp[i].val=new_val;
                    }
                    else{
                        dp[i].ind=ind+1;
                        dp[i].val=a[ind+1];
                    }
                }
            }
    }
    plata complet={n,0};
    for(i=1;i<(1<<m);++i)
        if(dp[i]==complet)
            return 1;
    return 0;
}

void write(bool ans){
    fout<<((ans)?"YES":"NO");
}

int main()
{
    read();
    write(get_dp());
    return 0;
}

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