1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <set>
#include <bitset>

using namespace std;

unsigned rozwiaz(vector<unsigned>, vector<unsigned>);

int main() {
  unsigned n,m;
  cin >> n >> m;
  vector<unsigned> rzeczy; rzeczy.reserve(n);
  copy_n(istream_iterator<unsigned>(cin), n, back_inserter(rzeczy));   //Boje sie tego copy_n, bo na szkopule sie psul... a byl kod dobry :s
  vector<unsigned> plecaki; plecaki.reserve(m);
  copy_n(istream_iterator<unsigned>(cin), m, back_inserter(plecaki));
  sort(begin(rzeczy), end(rzeczy));
  sort(begin(plecaki), end(plecaki), greater<unsigned>());
  while(plecaki.back() < rzeczy.front())
   plecaki.pop_back();
  const unsigned odpowiedz = (plecaki.empty() == false) ? rozwiaz(move(rzeczy), move(plecaki)) : 0;
  if(odpowiedz != 0)
   cout << odpowiedz << '\n';
  else
   cout << "NIE\n";
 }

vector<unsigned> jeden_plecak(vector<unsigned> rzeczy, const unsigned pojemnosc) {
  if(rzeczy.empty())
   return vector<unsigned>();
  unsigned maks_waga = 0, kiedy = 0;
  for(unsigned i = 0; i < (1U << rzeczy.size()); ++i) {
    bitset<24> bity(i);
    unsigned long long waga = 0;
    for(unsigned j = 0; j < rzeczy.size(); ++j) {
      waga += rzeczy[j] * bity[j];
     }
    if(waga <= pojemnosc && maks_waga < waga) {
      maks_waga = waga;
      kiedy = i;
     }
    if(waga == pojemnosc)
     break;
   }
  vector<unsigned> to_del;
  for(unsigned i = 0; i < rzeczy.size(); ++i) {
    bitset<24> bity(kiedy);
    if(bity[i])
     to_del.push_back(rzeczy[i]);
   }
  return to_del;
 }

vector<unsigned> przyciety(const vector<unsigned>& rzeczy, const unsigned pojemnosc) {
  auto it = find_if(begin(rzeczy), end(rzeczy), [=](unsigned x){return x > pojemnosc;});
  return vector<unsigned>(begin(rzeczy), it);
 }

bool sprawdz(vector<unsigned> rzeczy, vector<unsigned> plecaki) {
  while(!plecaki.empty()) {
    auto to_del = jeden_plecak(przyciety(rzeczy, plecaki.back()), plecaki.back());
    for(const auto& x : to_del) {
      auto it = find(begin(rzeczy), end(rzeczy), x);
      rzeczy.erase(it);
     }
    plecaki.pop_back();
   }
  return rzeczy.empty();
 }

unsigned rozwiaz(vector<unsigned> rzeczy, vector<unsigned> plecaki) {
  auto suma = accumulate(begin(rzeczy), end(rzeczy), 0ULL);
  if(suma > accumulate(begin(rzeczy), end(rzeczy), 0ULL))
   return 0;
  unsigned i = 0;
  for(unsigned long long suma_lokalna = 0; suma_lokalna < suma && i < plecaki.size(); ++i)
   suma_lokalna += plecaki[i];
  for(; i <= plecaki.size(); ++i) {
    if(sprawdz(rzeczy, vector<unsigned>(begin(plecaki), begin(plecaki)+i)))
     return i;
   }
  return 0;
 }