제출 #456409

#제출 시각아이디문제언어결과실행 시간메모리
456409ak2006은행 (IZhO14_bank)C++14
25 / 100
2 ms440 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int main()
{
    setIO();
    int n,m;
    cin>>n>>m;
    
    int maxSet = (1<<m);
    
    vi leftOver(maxSet);
    vi numFilled(maxSet,-1);
    vi a(n + 1),b(m);

    for (int i = 1;i<=n;i++)cin>>a[i];
    for (int i = 0;i<m;i++)cin>>b[i];


    numFilled[0] = 0;
    leftOver[0] = 0;

    for (int mask = 0;mask < maxSet;mask++){
        for (int i = 0;i<m;i++){
            if (mask & (1<<i)){
                int prevMask = mask - (1<<i);

                if (numFilled[prevMask] == -1)continue;
                
                if (leftOver[prevMask] + b[i] < a[numFilled[prevMask] + 1]){
                    numFilled[mask] = numFilled[prevMask];
                    leftOver[mask] = leftOver[prevMask] + b[i];
                }

                else if (leftOver[prevMask] + b[i] == a[numFilled[prevMask] + 1]){
                    numFilled[mask] = numFilled[prevMask] + 1;
                    leftOver[mask] = 0;
                }
            }
        }
    }
    //cout<<numFilled[maxSet - 1]<<endl;
    if (numFilled[maxSet - 1] == n)cout<<"YES";
    else cout<<"NO";
    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...