Submission #1000992

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000992		asdasdqwer	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	396 ms	19028 KiB

bobek

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

#define int int64_t
#define pii array<int,2>

int vals[2'000'000];
int pf[2'000'000];


signed main() {
  clock_t start = clock();

  int n,m;cin>>n>>m;
  vector<int> v(n);
  for (auto &x:v)cin>>x;
  
  int cnt=0;

  if (n <= 23) {
    for (int i=0;i<(1<<n);i++) {
      int cst=0;

      for (int j=0;j<n;j++) {
        if ((i & (1<<j)) == 0) continue;
          cst += v[j];
        }

      if (cst <= m) cnt++;
    }

    cout<<cnt<<"\n";
    return 0;
  }

  int pt = 0;
  for (int i=0;i<(1<<20);i++) {
    int cst = 0;
    for (int j=0;j<20;j++) {
      if ((i & (1<<j)) == 0) continue;
      cst += v[j];
    }

    if (cst > m) continue;
    cnt++;
    vals[pt++] = cst;
  }

  sort(vals, vals+pt);

  pf[0] = 1;
  int pt2 = 0;

  for (int i=1;i<pt;i++) {
    if (vals[i] == vals[i-1]) {
      pf[pt2]++;
    }

    else {
      pt2++;
      vals[pt2] = vals[i];
      pf[pt2]++;
    }
  }

  pt2++;
  vals[pt2]=0;
  for (int i=1;i<pt2;i++) pf[i] += pf[i-1];

  auto bns=[&](int num) {
    int l = 0, r = pt2-1;
    int ans = -1;
    while (l <= r) {
      int mid = l + ((r-l)>>1);
      if (vals[mid] + num <= m) {
        ans = mid;
        l = mid+1;
      }

      else {
        r = mid-1;
      }
    }

    return pf[ans];
  };

  for (int i=1;i<(1<<(n-20));i++) {
    int cst = 0;
    for (int j=0;j<n-20;j++) {
      if ((i & (1<<j)) == 0) continue;
      cst += v[j + 20];
    }

    if (cst > m) continue;
    cnt += bns(cst);
  }

  cout<<cnt<<"\n";
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:13:11: warning: unused variable 'start' [-Wunused-variable]
   13 |   clock_t start = clock();
      |           ^~~~~

• 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