oj.uz

Submission #1105258

# Submission time Handle Problem Language Result Execution time Memory
1105258 2024-10-25T21:20:22 Z joelgun14 Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 426 ms 22960 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
// Joel's solution
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n; ll m;
  cin >> n >> m;
  ll a[n];
  for(int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  if(n <= 5) {
    int res = 0;
    for(int i = 0; i < 1 << n; ++i) {
      ll sum = 0;
      for(int j = 0; j < n; ++j) {
        if((1 << j) & i)
          sum += a[j];
      }
      if(sum <= m) {
        ++res;
      }
    }
    cout << res << endl;
  }
  else {
    vector<ll> v1, v2;
    for(int i = 0; i < 1 << n / 2; ++i) {
      ll sum = 0;
      for(int j = 0; j < n / 2; ++j) {
        if((1 << j) & i)
          sum += a[j];
      }
      if(sum <= m)
        v1.pb(sum);
    }
    for(int i = 0; i < 1 << (n - n / 2); ++i) {
      ll sum = 0;
      for(int j = 0; j < n - n / 2; ++j) {
        if((1 << j) & i)
          sum += a[j + n / 2];
      }
      if(sum <= m)
        v2.pb(sum);
    }
    ll res = 0;
    sort(v2.begin(), v2.end());
    for(auto x : v1) {
      res += ub(v2.begin(), v2.end(), m - x) - v2.begin();
    }
    cout << res << endl;
  }
  return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 504 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2132 KB Output is correct
2 Correct 80 ms 6600 KB Output is correct
3 Correct 426 ms 22960 KB Output is correct
4 Correct 80 ms 6600 KB Output is correct
5 Correct 13 ms 1572 KB Output is correct
6 Correct 6 ms 1104 KB Output is correct
7 Correct 7 ms 464 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3020 KB Output is correct
2 Correct 28 ms 2132 KB Output is correct
3 Correct 174 ms 12624 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 980 KB Output is correct
6 Correct 14 ms 1744 KB Output is correct
7 Correct 7 ms 504 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 4688 KB Output is correct
2 Correct 112 ms 8772 KB Output is correct
3 Correct 131 ms 8780 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 66 ms 8780 KB Output is correct
6 Correct 201 ms 22860 KB Output is correct
7 Correct 36 ms 336 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 14912 KB Output is correct
2 Correct 28 ms 2132 KB Output is correct
3 Correct 9 ms 1104 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 1104 KB Output is correct
6 Correct 181 ms 14908 KB Output is correct
7 Correct 7 ms 336 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2132 KB Output is correct
2 Correct 75 ms 6600 KB Output is correct
3 Correct 8 ms 1104 KB Output is correct
4 Correct 8 ms 980 KB Output is correct
5 Correct 60 ms 8780 KB Output is correct
6 Correct 23 ms 2132 KB Output is correct
7 Correct 99 ms 336 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 315 ms 22864 KB Output is correct
2 Correct 27 ms 2132 KB Output is correct
3 Correct 8 ms 1104 KB Output is correct
4 Correct 352 ms 22852 KB Output is correct
5 Correct 99 ms 10684 KB Output is correct
6 Correct 13 ms 1744 KB Output is correct
7 Correct 13 ms 336 KB Output is correct