Submission #1127105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127105		Shifted777	Bank (IZhO14_bank)	C++20	100 / 100	91 ms	8520 KiB

bank

#ifdef LOCAL
#include "bits/stdc++.h"
#else 
#include <bits/stdc++.h>
#endif
using namespace std;

// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// template <class T> using ind_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define sz(x) (int)(x).size()
#define sq(x) (x) * (x)
#define all(x) x.begin(), x.end()
#define f first
#define s second
#define pb push_back
#define popcnt __builtin_popcount
#define bk back()
 
#define ll long long
#define cd complex<double>
#define pii pair<int,int>
#define vpii vector<pii>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vvll vector<vector<ll>>

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define F0R(i, a) for (int i = 0; i < (a); ++i)
#define ROF(i, a, b) for (int i = (a)-1; i >= (b); --i)
#define R0F(i, a) for (int i = (a)-1; i >= 0; --i)
#define each(a, x) for (auto& a: x)

string to_string(string s) {
    return '"' + s + '"';
}

string to_string(char c) {
    return '\'' + string(1,c) + '\'';
}

string to_string(const char* s) {
  return to_string((string)s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
template <typename T1, typename T2>
string to_string(pair<T1, T2> &p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename T>
string to_string(T v) {
    int c = 0;
    string res = "{";
    for (const auto &x : v) {
        if (c) res += ", ";
        c = 1;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
void __print(bool b) { cerr << "]" << endl; }
 
template <typename First, typename... Rest>
void __print(bool b, First F, Rest... R) {
    if (b) cerr << ", ";
    cerr << to_string(F);
    __print(true, R...);
}

#ifdef LOCAL
#define print(...) cerr << "[" << #__VA_ARGS__ << "] : [", __print(false, __VA_ARGS__)
#else
#define print(...) 42
#endif
 
mt19937_64 rv(chrono::steady_clock::now().time_since_epoch().count());
ll rng(ll l, ll r) { return (ll)uniform_int_distribution<ll>(l, r)(rv); }
 
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
 
    size_t operator()(uint64_t x) const {
        static const uint64_t r = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + r);
    }
};

ll MOD = 1e9+7;
int M998 = 998244353;
const ll INF = 3e18;
const double PI = 4 * atan(1); 
const int dx[4] {1, 0, -1, 0}, dy[4] {0, 1, 0, -1};
 
ll min(int a, ll b) { return min((ll)a, (ll)b); }
ll min(ll a, int b) { return min((ll)a, (ll)b); }
template<class T> bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

ll p2(int b) { return (1ll << b); }
int l2(int x) { return 31 - __builtin_clz(x); }
int l2(ll x) { return 63 - __builtin_clzll(x); }

ll msum(ll a, ll b, ll m = MOD) { return ((a + b) % m + m) % m; }
ll mdif(ll a, ll b, ll m = MOD) { return ((a - b) % m + m) % m; }
ll minc(ll &a, ll b, ll m = MOD) { return a = ((a + b) % m + m) % m; }
ll minc(int &a, ll b, ll m = MOD) { return a = ((a + b) % m + m) % m; }
ll mdec(ll &a, ll b, ll m = MOD) { return a = ((a - b) % m + m) % m; }
ll mdec(int &a, ll b, ll m = MOD) { return a = ((a - b) % m + m) % m; }
ll mmul(ll a, ll b, ll m = MOD) { return (__int128)a * b % m; } 
ll mexp(ll b, ll e, ll m = MOD) {
    ll res = 1;
    while (e) {
        if (e % 2) res = mmul(res, b, m);
        b = mmul(b, b, m);
        e /= 2;
    } return res;
}
ll exp(ll b, ll e) { return mexp(b, e, INF); }
ll inv(ll b, ll m = MOD) { return mexp(b, m-2, m); }
ll mdiv(ll a, ll b, ll m = MOD) { return mmul(a, inv(b), m); }

struct DSU {
    vector<int> p, c;

    DSU(int n) : c(n, 1), p(n) { for (int i = 0; i < n; ++i) p[i] = i; }

    int get(int v) {
        if (p[v] == v) return v;
        return p[v] = get(p[v]);
    }

    int size(int v) { return c[get(v)]; }

    bool same(int x, int y) { return get(x) == get(y); }

    bool unite(int x, int y) {
        x = get(x); y = get(y); 
        if (x == y) return 0;
        if (c[x] > c[y]) swap(x, y);
        p[x] = y;
        c[y] += c[x];
        return 1;
    }
};

template <class T> struct BIT {
    int len; vector<T> bit, v;

    BIT(int n) : len(n), bit(n + 1), v(n) {}

    void edit(int ind, T val) { add(ind, val - v[ind]); }

    void add(int ind, T val) {
        v[ind] += val;
        ind++;
        for (; ind <= len; ind += ind & -ind) { bit[ind] += val; }
    }

    T sum(int ind) { // [0, ind]
        ind++;
        T total = 0;
        for (; ind > 0; ind -= ind & -ind) { total += bit[ind]; }
        return total;
    }

    T sum(int l, int r) { // [l, r)
        return sum(r - 1) - sum(l - 1);
    }
};

template<typename T> struct SegTree {
    vector<T> v; int len;

    T id = 0;
    T oper(T a, T b) {
        return a + b;
    }

    SegTree(int n) : len(n), v(n*2) { for (int i = 0; i < n*2; ++i) v[i] = id; }
    SegTree(vector<T> v_) : len(sz(v_)), v(v_) {}

    void edit(int ind, const T &val) {
        ind += len; v[ind] = val;
        while (ind > 1) {
            ind /= 2;
            v[ind] = oper(v[ind<<1], v[ind<<1|1]);
        }
    }

    T query(int l, int r) { // [l,r)
        T resl = id, resr = id; l += len; r += len;
        while (l < r) {
            if (l%2) resl = oper(resl, v[l++]);
            if (r%2) resr = oper(v[--r], resr);
            l /= 2; r /= 2;
        }
        return oper(resl, resr);
    }

    T get(int ind) { return v[ind + len]; }

    void inc(int ind, T val) { edit(ind, get(ind) + val); }
};

 
void solve(int tc = 0){
    int n, m; cin >> n >> m;
    vi a(n), b(m); 
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) cin >> b[i];
    vpii dp(1 << m, {0, 0});
    for (int j = 0; j < (1 << m); ++j) {
        for (int i = 0; i < m; ++i) {
            if (j & (1 << i)) continue;
            if (dp[j].f == n) {
                dp[j | (1 << i)] = dp[j];
                continue;
            }
            if (dp[j].s + b[i] == a[dp[j].f]) chmax(dp[j | (1 << i)], {dp[j].f + 1, 0});
            else chmax(dp[j | (1 << i)], {dp[j].f, dp[j].s + b[i]});
        }
    }
    if (dp[(1 << m) - 1].f == n) cout << "YES\n";
    else cout << "NO\n";
}

void init() {
    //
}

void setio(string s = "") {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // return;
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("err.txt", "w", stderr);
    freopen("out.txt", "w", stdout);
    #else
    if (sz(s)) {
        freopen((s+".in").c_str(), "r", stdin);
        freopen((s+".out").c_str(), "w", stdout);
    }
    #endif
}
 
int32_t main() {
    setio();
    init();

    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) solve(i);
 
    cerr << "Time : " << (double) clock() / CLOCKS_PER_SEC << "s" << endl;
    return 0;
}   

Compilation message (stderr)

bank.cpp: In function 'void setio(std::string)':
bank.cpp:258:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  258 |         freopen((s+".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:259:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  259 |         freopen((s+".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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