Submission #1351976

#TimeUsernameProblemLanguageResultExecution timeMemory
1351976bbbirosBank (IZhO14_bank)C++20
71 / 100
1094 ms836 KiB
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#define ll long long
#define X first
#define Y second
#define endl '\n'
using namespace std;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
vector<int> p;
vector<int> b;
int n,m;
void read()
{
    cin>>n>>m;
    p.resize(n);
    b.resize(m);
    for(int i=0;i<n;i++)
    {
        cin>>p[i];
    }
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
}
const int MAXN=20100;
vector<int> dp[MAXN+5];
int used[32];
bool rec(int sum,int i)
{
    if(i==n)return true;
    if(sum==0)
    {
        return rec(p[i+1],i+1);
    }
    for(int p:dp[sum])
    {
        if(!used[p])
        {
            used[p]=1;
            if(rec(sum-b[p],i))return true;
            used[p]=0;
        }
    }
    return false;
}
signed main()
{
    speed();
    read();
    dp[0].push_back(-1);
    for(int i=0;i<m;i++)
    {
        for(int j=MAXN;j>=0;j--)
        {
            if(dp[j].size())
            {
                dp[j+b[i]].push_back(i);
            }
        }
    }
    if(rec(p[0],0))
    {
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...