Submission #580405

#	Time	Username	Problem	Language	Result	Execution time	Memory
580405		duydong05	Bank (IZhO14_bank)	C++14	100 / 100	147 ms	16764 KiB

bank

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

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