Submission #1286322

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286322		dssfsuper2	Bank (IZhO14_bank)	C++20	100 / 100	159 ms	8240 KiB

bank

#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';
}

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