Submission #1313797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313797		nambanana987	Bank (IZhO14_bank)	C++20	100 / 100	105 ms	16836 KiB

bank

#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();
}

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