제출 #1348530

#제출 시각아이디문제언어결과실행 시간메모리
1348530vjudge1은행 (IZhO14_bank)C++20
100 / 100
75 ms16844 KiB
#ifdef LOCAL
#include <C:\Users\onlin\Desktop\competitive_programming\codes\debug.hpp>
#else
    #define dbg(x) 
    #define dbgl(x) 
    #define dbgvec(v) 
    #define DBG_OF(i, v)
#endif
#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define endl '\n'
#define all(v) v.begin(),v.end()
bool testcases=0;
int dx[]={-1,1,-1,1,2,2,-2,-2};
int dy[]={-2,-2,+2,2,-1,1,-1,1};
const int MOD=1e9+7;
const int inf=1e12;
const int ranint=65729178;
const int mynum=21;
const int N=3e5;
const int siz=N+mynum;
const int tsiz=4*siz;
void solve(){
    int n,m;
    cin>>n>>m;
    int v[m];
    int mny[n];
    for(int i=0;i<n;i++)cin>>mny[i];
    for(int i=0;i<m;i++)cin>>v[i];
    int dp[1<<m];
    int mx=-1;
    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    int sum[(1<<m)];
    memset(sum,0,sizeof(sum));
    for(int mask=0;mask<(1<<m);mask++){
        if(dp[mask]==-1)continue;
        if(dp[mask]==n){
            cout<<"YES"<<endl;
            return;
        }
        for(int i=0;i<m;i++){
            if(!((1<<i)&mask)){
                if(sum[mask]+v[i]<mny[dp[mask]]){
                    if(dp[mask|(1<<i)]>dp[mask])continue;
                    dp[mask|(1<<i)]=dp[mask];
                    sum[mask|(1<<i)]=sum[mask]+v[i];
                }
                else if(sum[mask]+v[i]==mny[dp[mask]]){
                    if(dp[mask|(1<<i)]>dp[mask]+1)continue;
                    dp[mask|(1<<i)]=dp[mask]+1;
                    sum[mask|(1<<i)]=0;
                }
            }
        }
    }
    cout<<"NO"<<endl;
}
signed main() {
    iostream::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    if(testcases)cin>>t;
    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...