oj.uz

Submission #854995

# Submission time Handle Problem Language Result Execution time Memory
854995 2023-09-29T17:26:54 Z tvladm2009 Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 340 ms 21940 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 40 + 7;
ll a[N];
ll n, x;

signed main() {
#ifdef ONPC
  freopen ("input.txt", "r", stdin);
#else
  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif // ONPC

  cin >> n >> x;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  int half1 = (n + 1) / 2;
  int half2 = n - half1;
  vector<ll> v1, v2;
  for (int mask = 0; mask < (1 << half1); mask++) {
    ll s = 0;
    for (int b = 0; b < half1; b++) {
      if (mask & (1 << b)) {
        s += a[b + 1];
      }
    }
    v1.push_back(s);
  }
  for (int mask = 0; mask < (1 << half2); mask++) {
    ll s = 0;
    for (int b = 0; b < half2; b++) {
      if (mask & (1 << b)) {
        s += a[half1 + b + 1];
      }
    }
    v2.push_back(s);
  }
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  ll print = 0;
  for (auto &it : v1) {
    int low = 0, high = (int) v2.size() - 1, sol = -1;
    while (low <= high) {
      int mid = (low + high) / 2;
      if (v2[mid] <= x - it) {
        low = mid + 1;
        sol = mid;
      } else {
        high = mid - 1;
      }
    }
    print += sol + 1;
  }
  cout << print << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 536 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 452 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 428 KB Output is correct
4 Correct 1 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 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2516 KB Output is correct
2 Correct 80 ms 5660 KB Output is correct
3 Correct 340 ms 20992 KB Output is correct
4 Correct 78 ms 5832 KB Output is correct
5 Correct 13 ms 1496 KB Output is correct
6 Correct 8 ms 992 KB Output is correct
7 Correct 17 ms 1756 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2944 KB Output is correct
2 Correct 28 ms 2516 KB Output is correct
3 Correct 131 ms 11024 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 1116 KB Output is correct
6 Correct 16 ms 1708 KB Output is correct
7 Correct 16 ms 1500 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 4564 KB Output is correct
2 Correct 134 ms 8636 KB Output is correct
3 Correct 120 ms 8580 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 77 ms 8588 KB Output is correct
6 Correct 276 ms 21688 KB Output is correct
7 Correct 108 ms 8640 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 16900 KB Output is correct
2 Correct 27 ms 2520 KB Output is correct
3 Correct 9 ms 992 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 7 ms 1056 KB Output is correct
6 Correct 226 ms 16740 KB Output is correct
7 Correct 18 ms 1632 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2520 KB Output is correct
2 Correct 75 ms 5588 KB Output is correct
3 Correct 9 ms 1116 KB Output is correct
4 Correct 9 ms 1112 KB Output is correct
5 Correct 83 ms 8600 KB Output is correct
6 Correct 28 ms 2520 KB Output is correct
7 Correct 300 ms 21940 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 21432 KB Output is correct
2 Correct 30 ms 2516 KB Output is correct
3 Correct 9 ms 992 KB Output is correct
4 Correct 327 ms 20984 KB Output is correct
5 Correct 109 ms 11196 KB Output is correct
6 Correct 18 ms 1752 KB Output is correct
7 Correct 33 ms 3032 KB Output is correct