Submission #496091

#	Time	Username	Problem	Language	Result	Execution time	Memory
496091		shmad	Bank (IZhO14_bank)	C++14	100 / 100	138 ms	25172 KiB

bank

    #include <bits/stdc++.h>
     
    #define int long long
    #define vt vector
    #define pb push_back
    #define all(x) (x).begin(), (x).end()
    #define sz(x) (int)(x).size()
    #define ff first
    #define ss second
    #define dbg(x) cerr << #x << " = " << x << '\n'
     
    using namespace std;
    using ll = long long;
    using pii = pair<int, int>;
    using vvi = vt< vt<int> >;
     
    const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18 + 7, B = 500, LIM = (1ll << 20);
     
    int n, m;
    vt<int> dp(LIM, -1), lft(LIM, -1), ans;
     
    bool bit (int x, int i) {
      return (x >> i & 1);
    }
     
    bool check (int x) {
      return (x == n);
    }
     
    void solve () {
      cin >> n >> m;
      vt<int> a(n), b(m);
      for (int &i: a) cin >> i;
      for (int &i: b) cin >> i;
      dp[0] = lft[0] = 0;
      for (int mask = 0; mask < (1 << m); mask++) {
        for (int i = 0; i < m; i++) {
          if (bit(mask, i)) {
            int mask1 = mask ^ (1 << i);
            if (dp[mask1] == -1) continue;
            int cur = lft[mask1] + b[i], j = dp[mask1];
            if (cur > a[j]) continue;
            dp[mask] = dp[mask1] + (cur == a[j]);
            if (cur < a[j]) lft[mask] = cur;
            if (cur == a[j]) lft[mask] = 0;
          }
        }
        ans.pb(dp[mask]);
      }                                
      cout << (any_of(all(ans), check) ? "YES" : "NO");
      cout << '\n';
    }
     
    bool testcases = 0;
     
    signed main() {
      cin.tie(0) -> sync_with_stdio(0);
      int test = 1;
      if (testcases) cin >> test;
      for (int cs = 1; cs <= test; cs++) {
        solve();
      }
    }

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