Submission #175867

#	Time	Username	Problem	Language	Result	Execution time	Memory
175867		Pankin	Bank (IZhO14_bank)	C++14	100 / 100	170 ms	1528 KiB

bank

#include <bits/stdc++.h>

/*
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
*/

#define mp make_pair
#define ll long long
#define ld long double
#define pb push_back
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fs first
#define sc second
#define getfiles ifstream cin("input.txt"); ofstream cout("output.txt");
#define endl '\n'
#define con continue
#define pii pair<int, int>
#define all(x) x.begin(), x.end()

const int INF = 2000000005;
const ll BIG_INF = 2000000000000000005;
const int mod = 1000000007;
const int P = 31;
const ld PI = 3.141592653589793238462643;
const double eps = 1e-9;

using namespace std;

vector< pair<int, int> > dir = {
    {
        -1, 0
    },
    {
        0, 1
    },
    {
        1, 0
    },
    {
        0, -1
    }
};

bool valid(int x, int y, int n, int m) {
    return x >= 0 && y >= 0 && x < n && y < m;
}

mt19937 rng(1999999973);

const int N = 22;
int a[N], b[N], pref[N], n, m;
bool can[1 << (N - 1)];

signed main() {
    fast_io;

//    ifstream cin("bank.in");
//    ofstream cout("bank.out");

    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    pref[0] = a[0];
    for (int i = 1; i < n; i++)
        pref[i] = a[i] + pref[i - 1];
    pref[n] = INF;

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

    can[0] = true;

    for (int mask = 0; mask < (1 << m); mask++) {
        if (!can[mask])
            continue;
        int cur = 0, sum = 0;
        for (int i = 0; i < m; i++) {
            if (((mask>>i)&1) == 1)
                sum += b[i];
        }

        while(pref[cur] <= sum)
            cur++;

        if (cur == n) {
            cout << "YES";
            return 0;
        }

        for (int i = 0; i < m; i++) {
            if (((mask>>i)&1) == 0 && sum + b[i] <= pref[cur])
                can[mask | (1 << i)] = true;
        }
    }

    cout << "NO";

    return 0;
}

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