Submission #624818

#	Time	Username	Problem	Language	Result	Execution time	Memory
624818		sam_28	Bank (IZhO14_bank)	C++17	100 / 100	163 ms	8640 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>     // Including tree_order_statistics_node_update

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<double, double> pd;
typedef vector<ll> vl;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))
#define SWAP(type, a, b)    \
    {                       \
        const type tmp = a; \
        a = b;              \
        b = tmp;            \
    }
#define rep(i, l, r) for (ll i = (l); i < (r); i++)
#define per(i, l, r) for (ll i = (l); i >= (r); i--)
#define dbg(x) cout << #x << " = " << x << ln
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define tc    \
    ll t;     \
    cin >> t; \
    while (t--)
#define godspeed                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define NO cout << "NO" \
                << "\n"
#define YES cout << "YES" \
                 << "\n"
#define clr(x, y) memset(x, y, sizeof(x))
#define setbits(x) __builtin_popcountll(x)
#define mod 1000000007

template <class T>
bool ckmin(T &a, const T &b)
{
    return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

const ll inf = 1e9;
const ll llinf = 2e18;
ll MULL(ll a, ll b)
{
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
}
ll POWER(ll a, ll b)
{
    a %= mod;
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = MULL(res, a);
        a = MULL(a, a);
        b >>= 1;
    }
    return res;
}

void solve()
{
    int n, m;
    cin >> n >> m;
    vi people(n);
    for (int i = 0; i < n; i++)
    {
        cin >> people[i];
    }
    vi salary(m);
    for (int i = 0; i < m; i++)
    {
        cin >> salary[i];
    }
    vi people_covered(1 << m, -1);
    vi left_money(1 << m);
    people_covered[0] = 0;
    left_money[0] = 0;
    for (int mask = 0; mask < (1 << m); mask++)
    {
        for (int last = 0; last < m; last++)
        {
            if (mask & (1 << last))
            {
                int prevMask = mask ^ (1 << last);
                if (people_covered[prevMask] == -1)
                {
                    continue;
                }

                int newAmt = salary[last] + left_money[prevMask];
                int target = people[people_covered[prevMask]];
                if (target > newAmt)
                {
                    left_money[mask] = max(left_money[mask], newAmt);
                    people_covered[mask] = people_covered[prevMask];
                }
                else if (target == newAmt)
                {
                    left_money[mask] = 0;
                    people_covered[mask] = people_covered[prevMask] + 1;
                }
            }
        }
    }
    for (int i = 0; i < (1 << m); i++)
    {
        if (people_covered[i] == n)
        {
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
    return;
}

int main()
{
    godspeed;
    //    #ifndef ONLINE_JUDGE
    //       freopen("input.txt", "r", stdin);
    //       freopen("output.txt", "w", stdout);
    //    #endif
    solve();
    return 0;
}

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