Submission #1193344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193344		lopkus	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	385 ms	8828 KiB

bobek

#include <bits/stdc++.h>

#define int int64_t

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector<int> a(n);
  for(int i = 0; i < n; i++) {
    std::cin >> a[i];
  }
  std::vector<int> l, r;
  for(int i = 0; i < n / 2; i++) {
    l.push_back(i);
  }
  for(int i = n / 2; i < n; i++) {
    r.push_back(i);
  }
  int ans = 0;
  std::vector<int> left;
  for(int mask = 0; mask < (1LL << (int)l.size()); mask++) {
    int sum = 0;
    for(int i = 0; i < l.size(); i++) {
      if(mask & (1LL << i)) {
        sum += a[l[i]];
      }
    }
    ans += (sum <= m);
    if(mask != 0)
      left.push_back(sum);
  }
  std::sort(left.begin(), left.end());
  for(int mask = 1; mask < (1LL << (int)r.size()); mask++) {
    int sum = 0;
    for(int i = 0; i < r.size(); i++) {
      if(mask & (1LL << i)) {
        sum += a[r[i]];
      }
    }
    ans += (sum <= m);
    int L = 0, R = left.size() - 1, p = - 1;
    while(L <= R) {
      int mid = (L + R) / 2;
      if(sum + left[mid] <= m) {
        L = mid + 1;
        p = mid;
      }
      else {
        R = mid - 1;
      }
    }
    ans += p + 1;
  }
  std::cout << ans;
}

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10