Submission #1693730

---

Source Code Expand

#include <vector>
#include <iostream>
#include <assert.h>
#include <algorithm>

#define Unknown 2
#define No 0
#define Yes 1

int n, k, max;
std::vector<unsigned char> v;
std::vector<int> box;

void init() {
  std::sort(box.begin(), box.end(), std::greater<int>());
  max = box[0];
  v.resize(max + 1, Unknown);

  for(int i = 0; i < n; i++) {
    int a = box[i];
//    std::cout << a << "\n";
    v[a] = Yes;
    for(int j = i + 1; j < n; j++) {
      const int diff = a - box[j];
//      std::cout << a << " - " << box[j] << " = " << diff << "\n";
//      std::cout << diff << "\n";
      v[diff] = Yes;
    }
  }
}

bool configurable(int n) {
  if(max < n || n <= 0)
    return false;

  //std::cout << "? " << n << "\n";
  if(v[n] != Unknown) {
    //std::cout << "P(" << n << ") = " << v[n] << "\n";
    return v[n] == Yes;
  }
  v[n] = No;
  for(int x = 1; x <= max - n; x++) {
    if(configurable(n + x) && configurable(x)) {
      //std::cout << n << " = (" << (n + x) << " - " << x << ")\n";
      v[n] = Yes;
      return true;
    }
  }
  return false;
}

int main() {
  std::cin >> n;
  std::cin >> k;
  box.resize(n);

  for(int i = 0; i < n; i++) {
    std::cin >> box[i];
  }
  init();
  if(configurable(k)) {
    std::cout << "POSSIBLE\n";
  } else {
    std::cout << "IMPOSSIBLE\n";
  }
  return 0;
}

Submission Info

Judge Result