Submission #485987

#	Time	Username	Problem	Language	Result	Execution time	Memory
485987		keertan	Bank (IZhO14_bank)	C++17	100 / 100	170 ms	8520 KiB

bank

/**
 * If you live in imaginary world when your imaginary situation encounter in 
 * real situation you can't enjoiy it because you have to do pending work.
 * {This pending work appeared because you wasted that time for your useless
 * imagianry thinking .}
 */
#include<bits/stdc++.h>
using namespace std;
//#define int  int64_t
#define all(x) x.begin(),x.end()
#define all1(x) x.rbegin(),x.rend()
const int N=2e5+5;

void solve(){
    int n,m;
    cin>>n>>m;
    int pers[n],cur[m];
    for (int i=0;i<n;i++){cin>>pers[i];}
    for (int i=0;i<m;i++){cin>>cur[i];}
    int dp[1<<m],remaining[1<<m];
    memset(dp,-1,sizeof(dp));
    memset(remaining,-1,sizeof(remaining));
    dp[0]=remaining[0]=0;
    for (int msk=1;msk<(1<<m);msk++){
        for (int bt=0;bt<m;bt++){
            int prv=msk^(1<<bt);
            if (dp[prv]==-1){continue;}
            int cura=remaining[prv]+cur[bt];
            int req=pers[dp[prv]];
            if (cura<req){
                dp[msk]=dp[prv];
                remaining[msk]=cura;
            }
            else if (cura==req){
                dp[msk]=dp[prv]+1;
                remaining[msk]=0;
            }
        }
        if (dp[msk]==n){
            cout<<"YES";
            return;
        }
    }
    cout<<"NO";
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tq=1;
    //cin>>tq;
    for (;tq;tq--){solve();}
}
//is a bruteforce possible?
//think greedier, make more assumptions
// if we you find solution using loop to decrease complexity use bs
//stuck for more than 5 minutes? move on 

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