Submission #1286322

#TimeUsernameProblemLanguageResultExecution timeMemory
1286322dssfsuper2Bank (IZhO14_bank)C++20
100 / 100
159 ms8240 KiB
#include <bits/stdc++.h>
using namespace std;
int dp[2000000];
int n, m;
int s=0;
vector<int> a, b;
bool dpf(int x){
    if(dp[x]!=-1)return dp[x];
    int cs=0;
    int tf=0;
    int as=0;
    for(int i = 0;i<m;i++){
        if(x&(1<<i))cs+=b[i];
        while(tf<n && as+a[tf]<=cs){
            as+=a[tf];
            tf++;
        }
    }
    if(tf==n)return true;
    int rtp=cs-as;
    bool res=false;
    for(int i = 0;i<m;i++){
        if((!(x&(1<<i))) && a[tf]>=rtp+b[i] && dpf(x|(1<<i)))res=true;
    }
    dp[x]=res;
    return res;
}

int main(){
    cin>>n>>m;
    a.resize(n);b.resize(m);
    for(int&p:a){
        cin>>p;
        s+=p;
    }
    for(int&p:b)cin>>p;
    for(int i = 0;i<2000000;i++)dp[i]=-1;
    cout << (dpf(0)? "YES":"NO") << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...