Submission #337068

#	Time	Username	Problem	Language	Result	Execution time	Memory
337068		boykut	Bank (IZhO14_bank)	C++14	71 / 100	734 ms	492 KiB

bank

#include <bits/stdc++.h>
 
using namespace std;

#define all(a) a.begin(),a.end()

vector < int > vec, a, b, used;
bool flag;

void rec(int sum, int x) {
  if (sum == 0) {
    if (vec.size() == x) {
      sort (b.begin(),b.end());
      //for (int i = 0; i < vec.size(); i++) cout << vec[i] << ' '; cout << '\n';
      do {
        int index = 0;
        bool ok = true;
        for (int i = 0; i < vec.size(); i++) {
          int cnt = vec[i], sum = 0, test = 0;
          while (cnt--) {
            sum += b[index];
            if (sum == a[i])
              test = 1;
            index++;
          }
          if (test == 0)
            ok = false;
        }
        if (ok) flag = 1;
      } while (next_permutation(b.begin(), b.end()));
    }
    return;
  }
  for (int i = (vec.empty()?1:vec.back()); i <= sum; i++) {
    vec.push_back(i);
    rec(sum - i, x);
    vec.pop_back();
  }
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  
  if (m < n) {
    cout << "NO\n";
    return 0;
  }
  
  a = vector < int > (n);
  b = vector < int > (m);
  used = vector < int > (m);
  
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  
  for (int i = 0; i < m; i++) {
    cin >> b[i];
  }  
  
  if (n <= 10 && m <= 10) {
    flag = 0;
    rec(m, n);
    flag ? cout << "YES\n" : cout << "NO\n";
  } else {
  
    if (n <= 20 && m <= 20) {
      int cnt = 0;
      
      for (int I = 0; I < n; I++) {
        int ok = 0, mn = -1, mnnum = -1;
        for (int i = 0; i < (1 << m); i++) {
          int sum = 0, num = i, index = m - 1, cnt1 = 0;
          while (num) {
            if ((num & 1) && !used[index]) {
              sum += b[index], cnt1++;
            }
            index--;
            num /= 2;
          }
          
          if (sum == a[I]) {
            if (mn == -1 || cnt1 < mn) {
              mn = cnt1;
              mnnum = i;
            }
          }
          
        }
        if (mn != -1) {
          cnt++;
          int index = m - 1;
          while (mnnum) {
            if ((mnnum & 1) && !used[index]) {
              used[index]  = 1;
            }
            index--;
            mnnum /= 2;
          }
        }
      }
      cnt == n ? cout << "YES\n" : cout << "NO\n";
    }
  }
  return 0;
}

Compilation message (stderr)

bank.cpp: In function 'void rec(int, int)':
bank.cpp:12:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   12 |     if (vec.size() == x) {
      |         ~~~~~~~~~~~^~~~
bank.cpp:18:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for (int i = 0; i < vec.size(); i++) {
      |                         ~~^~~~~~~~~~~~
bank.cpp: In function 'int main()':
bank.cpp:74:13: warning: unused variable 'ok' [-Wunused-variable]
   74 |         int ok = 0, mn = -1, mnnum = -1;
      |             ^~

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