Submission #580405

#TimeUsernameProblemLanguageResultExecution timeMemory
580405duydong05Bank (IZhO14_bank)C++14
100 / 100
147 ms16764 KiB
#include <bits/stdc++.h>
#define ll long long 
#define pii pair <int, int >
#define pll pair <ll, ll >
#define FOR(i,a,b ) for (int i =a; i <= b ;i++)
#define FORD(i,a,b) for (int i =a; i >= b ; i--)
using namespace std;
const ll nMax= 2e6 +5;
const ll oo =1e9;
const ll mod =1e9 +7;
ll n, m , salary[nMax], bankNotes[nMax] ;
//ll people[nMax], leftover[nMax];
int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m ;
    FOR(i, 0, n-1) cin >> salary[i] ;
    FOR(i, 0, m -1 ) cin >> bankNotes[i];
    vector <ll> leftover(1 << m , -1) , people(1 << m , -1);
    leftover[0] = 0;
    people[0] = 0;
    FOR(mask,  1, (1 << m ) - 1) {
        FOR(i, 0,  m -1) {
            if ((mask & (1 << i)) == 0 ) continue;
            int prev = mask ^ (1 << i ) ;
            if (people[prev]  == -1) continue;
            ll newamount = leftover[prev] + bankNotes[i];
            ll targetcur = salary[people[prev]];
            if (newamount < targetcur ) {
                people[mask] = people[prev] ;
                leftover[mask] = newamount;
            }
            else if (newamount == targetcur) {
                people[mask] = people[prev] +1;
                leftover[mask] = 0;
            }

        }
        if (people[mask] == n ) {
            cout  <<"YES";
            return 0;
        }
    } 
    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...