Submission #434621

#	Time	Username	Problem	Language	Result	Execution time	Memory
434621		fvogel499	Bank (IZhO14_bank)	C++14	100 / 100	135 ms	8552 KiB

bank

/*
File created on 06/21/2021 at 14:51:13.
Link to problem: https://oj.uz/problem/view/IZhO14_bank
Description: 
Time complexity: O()
Space complexity: O()
Status: DEV
Copyright: Ⓒ 2021 Francois Vogel
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define pb push_back
#define ins insert
#define cls clear

#define ll long long

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int siz = 20;

int nbPeople, nbBanknotes;
int people [siz];
int banknotes [siz];
int lp [1<<siz];
int lft [1<<siz];

void dp(int x) {
    if (lp[x] != -2) return;
    lp[x] = -1;
    lft[x] = 0;
    for (int i = 0; i < nbBanknotes; i++) if ((x>>i)&1) {
        int nx = x&~(1<<i);
        dp(nx);
        int locPref = lp[nx];
        int locLeft = lft[nx]+banknotes[i];
        if (locPref+1 < nbPeople and locLeft == people[locPref+1]) {
            locPref++;
            locLeft = 0;
        }
        if (locPref > lp[x] or (locPref == lp[x] and locLeft > lft[x])) {
            lp[x] = locPref;
            lft[x] = locLeft;
        }
    }
}

signed main() {
    cin.tie(0);
    // ios_base::sync_with_stdio(0);

    cin >> nbPeople >> nbBanknotes;
    for (int i = 0; i < nbPeople; i++) cin >> people[i];
    for (int i = 0; i < nbBanknotes; i++) cin >> banknotes[i];
    for (int i = 0; i < (1<<nbBanknotes); i++) lp[i] = -2;
    for (int i = 0; i < (1<<nbBanknotes); i++) {
        dp(i);
        if (lp[i] == nbPeople-1) {
            cout << "YES";
            return 0;
        }
    }
    cout << "NO";

    int d = 0;
    d++;
}

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