Submission #334153

#TimeUsernameProblemLanguageResultExecution timeMemory
334153AlexLuchianovBank (IZhO14_bank)C++14
100 / 100
193 ms4716 KiB
#include <iostream>
#include <vector>
#include <cassert>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 20;
int const lim = 20000;
int v[1 + nmax], sum[1 + nmax], bank[1 + nmax];
int spec[1 + lim];
int dp[(1 << nmax)];

int main() {
  int n, m;
  std::cin >> n >> m;
  for(int i = 1;i <= n; i++) 
    std::cin >> v[i];
  for(int i = 1;i <= n; i++)
    sum[i] = sum[i - 1] + v[i];
  for(int i = 1;i <= n; i++)
    spec[sum[i]] = i;
  
  for(int j = 0; j < m; j++)
    std::cin >> bank[j];

  for(int i = 1;i <= lim; i++)
    if(spec[i] == 0)
      spec[i] = spec[i - 1];
  dp[0] = 1;
  bool valid = false;
  for(int mask = 0; mask < (1 << m); mask++) 
    if(dp[mask] == 1) {
      int cost = 0;
      for(int j = 0; j < m; j++)
        if(0 < ((1 << j) & mask))
          cost += bank[j];
      for(int j = 0; j < m; j++)
        if(0 == ((1 << j) & mask)) {
          int cost2 = cost + bank[j];
          int mask2 = mask | (1 << j);
          if(spec[cost] == spec[cost2])
            dp[mask2] = dp[mask];
          else if(spec[cost] + 1 == spec[cost2] && sum[spec[cost2]] == cost2) {
            dp[mask2] = dp[mask];
            if(spec[cost2] == n)
              valid = true;
          }
        }
    }

  if(valid == true)
    std::cout << "YES\n";
  else
    std::cout << "NO\n";
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...