Submission #589731

#TimeUsernameProblemLanguageResultExecution timeMemory
589731Mrdiaar은행 (IZhO14_bank)C++14
100 / 100
103 ms8512 KiB
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define up(i,a,n) for (int i=a;i<=n;i++)
#define douwn(i,a,n) for (int i=a;i>=n;i--)
#define fi freopen("T.INP","r",stdin)
#define fo freopen("T.OUT","w",stdout)
#define pb push_back
#define fst first
#define sec second
#define emplace_back ep;
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef pair<int,int> qii;
typedef pair<qii,int> qqi;
const int inf=1e9+5;
const int mod=1e9+7;
const int maxn=1e5+5;
const int maxm=2e6+5;
int n,m;
int a[maxn],b[maxn];
qii dp[maxm];
int main(){
    //fi;fo;
    cin>>n>>m;
    up(i,1,n){
        cin>>a[i];
    }
    a[n+1]=inf;
    up(i,1,m){
        cin>>b[i];
    }
    dp[0]={1,0};
    up(i,1,(1<<m)-1){
        up(j,1,m){
            if(i&1<<(j-1)){
                int prev=i^(1<<(j-1));
                int nw=dp[prev].sec+b[j];
                if(nw<a[dp[prev].fst]){
                    dp[i]={dp[prev].fst,nw};
                }
                if(nw==a[dp[prev].fst]){
                    dp[i]={dp[prev].fst+1,0};
                }
            }
        }
    }
    cout<<(dp[(1<<m)-1].fst==n+1?"YES":"NO");
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...