Submission #790355

#	Time	Username	Problem	Language	Result	Execution time	Memory
790355		Anonymous_Guys	Bank (IZhO14_bank)	C++17	27 / 100	2 ms	468 KiB

bank

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;


using namespace __gnu_pbds;

template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define pb push_back
#define ii pair<int, int>
#define lol unsigned long long
#define lll __int128_t
#define fi first
#define se second
#define fou(i, a, b) for (int i = a; i <= b; ++i)
#define all(v) (v).begin(), (v).end()
#define MAX_N 10000000
#define el '\n'
#define BIT(mask, j) ((mask >> j) & 1)
#define MASK(x) (1LL << (x))
typedef unsigned long long ll;
const int mxN = 1e4 + 9;
const int MOD = (int)1e9 + 7;
const ll INF = (ll)4e18 + 7LL;

const int dx[] = {0, 1, 0, -1, 3, 0, -3, 0, 2, 2, -2, -2, 1, 1, -1, -1};
const int dy[] = {1, 0, -1, 0, 0, 3, 0, -3, 1, -1, 1, -1, 2, -2, 2, -2} ;



struct DSU {
    vector<int> par, rank;
    DSU() {}
    DSU(int n): par(n, -1), rank(n, -1) {}
    int root(int u) {
        return (par[u] < 0 ? u : par[u] = root(par[u]));
    }

    int sameSet(int u, int v) {
        return root(u) == root(v);
    }

    int size(int u) {
        return -par[root(u)];
    }
    int unite(int u, int v) {
        int x = root(u);
        int y = root(v);
        if (x == y) return 0;

        if (par[x] > par[y]) {
            swap(x,y);
        }
        par[x] += par[y];
        par[y] = x;
        return 1;
    }
};

int a[mxN], b[mxN];
pair<int, int> dp[(1LL << 20) + 9];
int dp2[mxN], ans[mxN];
int n, m;
map<int, int> mp;
void solve() {
    bool kt = true;
    fou(i, 1, n) {
        memset(dp2, 0, sizeof dp2);
        dp2[0] = 1;
        fou(j, 1, m) {
            for (int k = a[i]; k >= b[j]; --k) {
                if (dp2[k] == 0 && dp2[k - b[j]] == 1) {
                    dp2[k] = 1; ans[k] = k - b[j];
                }
            }
        }

        int j = a[i];
        bool ok = true;
        while(j > 0) {
            if (mp[j - ans[j]] == 0) {
                ok = false; break;
            }
            mp[j - ans[j]]--;
            j = ans[j];

        }
        if (!ok) {
            kt = false;
        //    cout << i <<" ";
            break;
        }
    }
    if (kt) cout << "YES";
    else cout <<"NO";
}
void solve2() {
    dp[0] = {1, 0};
    bool ok = false;
    fou(mask, 0 , MASK(m) - 1) {
        if (dp[mask].fi == n) {
            ok = true; break;
        }
        fou(i, 0, m - 1) {
            
            if (!BIT(mask, i)) {
                ii p;
                if (a[dp[mask].fi] == dp[mask].se + b[i + 1]) {
                    p = {dp[mask].fi + 1, 0};
                } else {
                    p = {dp[mask].fi, dp[mask].se + b[i + 1]};
                }
                dp[mask | MASK(i)] = max(dp[mask | MASK(i)], p);
            } 
        }
    }
    if (ok) cout << "YES";
    else cout <<"NO";
}
int32_t main() {
    if (fopen("bank.in", "r")) {
        freopen("bank.in" ,"r", stdin);
        freopen("bank.out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
     cin >> n >> m;
    fou(i, 1, n) cin >> a[i];
    fou(i, 1, m) cin >> b[i];

    //solve();
    solve2();
    return 0 ;
}

Compilation message (stderr)

bank.cpp: In function 'int32_t main()':
bank.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |         freopen("bank.in" ,"r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bank.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen("bank.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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