oj.uz

답안 #1000992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1000992 2024-06-18T12:21:53 Z asdasdqwer Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 396 ms 19028 KB 
#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

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

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 348 KB Output is correct
2 Correct 4 ms 344 KB Output is correct
3 Correct 9 ms 516 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 4 ms 600 KB Output is correct
6 Correct 73 ms 344 KB Output is correct
7 Correct 8 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 344 KB Output is correct
2 Correct 19 ms 444 KB Output is correct
3 Correct 5 ms 344 KB Output is correct
4 Correct 5 ms 440 KB Output is correct
5 Correct 74 ms 424 KB Output is correct
6 Correct 8 ms 344 KB Output is correct
7 Correct 8 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 126 ms 9844 KB Output is correct
2 Correct 151 ms 14008 KB Output is correct
3 Correct 357 ms 14264 KB Output is correct
4 Correct 148 ms 13140 KB Output is correct
5 Correct 106 ms 10580 KB Output is correct
6 Correct 121 ms 10580 KB Output is correct
7 Correct 70 ms 2476 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 9796 KB Output is correct
2 Correct 137 ms 11092 KB Output is correct
3 Correct 167 ms 10576 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 100 ms 10668 KB Output is correct
6 Correct 129 ms 10836 KB Output is correct
7 Correct 66 ms 2396 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 12992 KB Output is correct
2 Correct 172 ms 11192 KB Output is correct
3 Correct 157 ms 11896 KB Output is correct
4 Correct 19 ms 344 KB Output is correct
5 Correct 102 ms 8528 KB Output is correct
6 Correct 204 ms 9828 KB Output is correct
7 Correct 72 ms 2396 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 273 ms 17840 KB Output is correct
2 Correct 166 ms 17932 KB Output is correct
3 Correct 135 ms 18876 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 108 ms 10676 KB Output is correct
6 Correct 179 ms 19024 KB Output is correct
7 Correct 76 ms 2396 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 147 ms 18872 KB Output is correct
2 Correct 152 ms 19024 KB Output is correct
3 Correct 135 ms 19024 KB Output is correct
4 Correct 119 ms 16820 KB Output is correct
5 Correct 106 ms 10680 KB Output is correct
6 Correct 140 ms 19028 KB Output is correct
7 Correct 128 ms 2472 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 345 ms 18884 KB Output is correct
2 Correct 135 ms 19024 KB Output is correct
3 Correct 133 ms 19024 KB Output is correct
4 Correct 396 ms 18868 KB Output is correct
5 Correct 114 ms 10580 KB Output is correct
6 Correct 136 ms 18872 KB Output is correct
7 Correct 64 ms 2396 KB Output is correct