Submission #645228

#	Time	Username	Problem	Language	Result	Execution time	Memory
645228		Trent	Bank (IZhO14_bank)	C++17	100 / 100	113 ms	1488 KiB

bank

#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"

using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define open(g) string _name_ = g; freopen((_name_ + ".in").c_str(), "r", stdin); freopen((_name_ + ".out").c_str(), "w", stdout)
#define printArr(a, len) for(int asdf = 0; asdf < (len); ++asdf) cout << (a)[asdf] << ' '; cout << '\n';
#define boost() cin.sync_with_stdio(0); cin.tie(0)
#define forR(i, x) for(int i = 0; i < x; ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(i) i.begin(), i.end()
#define pii pair<int, int>
#define vi vector<int>
#define si set<int>
#define usi unordered_set<int>
#define mii map<int, int>
#define umii unordered_map<int, int>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")

const int MN = 20;
int n, m;
int a[MN], b[MN];
int as[MN], bs[MN];
bool can[1 << MN];

inline int tot(int mask){
    int ret = 0;
    for(int i = 0; i < m; ++i) if(mask & (1 << i)) ret += b[i];
    return ret;
}

signed main(){
    cin >> n >> m;
    forR(i, n) {
        cin >> a[i];
        as[i] = i == 0 ? a[i] : as[i-1] + a[i];
    }
    forR(i, m) {
        cin >> b[i];
        bs[i] = i == 0 ? b[i] : bs[i-1] + b[i];
    }
    can[0] = true;
    REP(i, 1, 1 << m){
        int t = tot(i);
        int las = -1;
        forR(j, n) if(as[j] < t) las = j;
        int ct = las == -1 ? t : t - as[las];
        // cout << t << ' ' << las << ' ' << ct << '\n';
        for(int j = 0; j < m && !can[i]; ++j) can[i] = ((i & (1 << j)) > 0) && (b[j] <= ct) && (can[i ^ (1 << j)]);
    }
    bool pos = false;
    for(int i = 0; i < (1 << m) && !pos; ++i) if(can[i] && tot(i) == as[n-1]) pos = true;
    cout << (pos ? "YES\n" : "NO\n");
}

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