제출 #1313797

#제출 시각아이디문제언어결과실행 시간메모리
1313797nambanana987은행 (IZhO14_bank)C++20
100 / 100
105 ms16836 KiB
#include <bits/stdc++.h>
#include <climits>
using namespace std;
#define f first
#define s second
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define int long long
const int k=20;
const int N=(1<<k)+5;
int n,m;
int need[k+5],have[k+5];

int paid[N],leftover[N];
void solve(){
    cin>>n>>m;
    for(int i=0;i<n;++i) cin>>need[i];
    for(int i=0;i<m;++i) cin>>have[i];
    memset(paid,-1,sizeof(paid));memset(leftover,-1,sizeof(leftover));
    paid[0]=0;
    leftover[0]=0;
    for(int mask=0;mask<(1<<m);++mask){
        for(int i =0;i<m;++i){
            if(! (mask&(1<<i)))continue;
            int pre=mask& ~(1<<i);
            if(leftover[pre]==-1) continue;

            int new_money=leftover[pre]+have[i];
            int cur=need[paid[pre]];

            if(new_money<cur){
                leftover[mask]=new_money;
                paid[mask]=paid[pre];
            }

            else if(new_money==cur){
                leftover[mask]=0;
                paid[mask]=paid[pre]+1;
            }
        }

        if(paid[mask]==n){
            cout<<"YES";
            return;
        }
    }
    cout<<"NO";
}
signed main(){

    ios_base::sync_with_stdio(0);cin.tie(0);
    int T=1;
    while(T--) solve();
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...