Submission #337784

#	Time	Username	Problem	Language	Result	Execution time	Memory
337784		boykut	Bank (IZhO14_bank)	C++14	100 / 100	649 ms	82668 KiB

bank

#include <bits/stdc++.h>

using namespace std;

int dp[1 << 20][20];

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   
   int n, m;
   cin >> n >> m;
   int a[n], b[m];
   int mx;
   for (int i = 0; i < n; i++) cin >> a[i], mx = (i?max(mx, a[i]):a[i]);
   for (int i = 0; i < m; i++) cin >> b[i];
   vector <int> can[mx + 1];
   for (int i = 0; i < (1 << m); i++) {
      int index = m - 1, num = i, s = 0;
      while (num) {
         if (num & 1) s += b[index];
         index--;
         num >>= 1;
      }
      if (s <= mx)can[s].push_back(i);
   }
   
   for (int i = 0; i < can[a[0]].size(); i++) {
      dp[can[a[0]][i]][0] = 1;
   }
   
   bool ok = false;
   for (int i = 1; i < n; i++) {
      int find = 0;
      for (int mask = 0; mask < (1 << m); mask++) {
         if (!dp[mask][i - 1]) continue;
         for (int el : can[a[i]]) {
            if ((mask & el) == 0)
               dp[mask | el][i] = 1, find = 1;
         }
      }
      if (find == 0) break;
   }
   for (int mask = 0; mask < (1 << m); mask++) {
      if (dp[mask][n - 1]) ok = true;
   }
   ok ? cout << "YES\n" : cout << "NO\n";
   return 0;
}

Compilation message (stderr)

bank.cpp: In function 'int main()':
bank.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |    for (int i = 0; i < can[a[0]].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~
bank.cpp:17:24: warning: 'mx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   17 |    vector <int> can[mx + 1];
      |                     ~~~^~~

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