oj.uz

Submission #1105256

# Submission time Handle Problem Language Result Execution time Memory
1105256 2024-10-25T21:14:21 Z joelgun14 Ice Hockey World Championship (CEOI15_bobek) C++17
40 / 100
 386 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 <= 20) {
    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 << 20; ++i) {
      ll sum = 0;
      for(int j = 0; j < n; ++j) {
        if((1 << j) & i)
          sum += a[j];
      }
      if(sum <= m)
        v1.pb(sum);
    }
    for(int i = 0; i < 1 << (n - 20); ++i) {
      ll sum = 0;
      for(int j = 0; j < n - 20; ++j) {
        if((1 << j) & i)
          sum += a[j + 20];
      }
      if(sum <= m)
        v2.pb(sum);
    }
    ll res = v1.size() + v2.size();
    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 508 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 7 ms 508 KB Output is correct
2 Correct 4 ms 336 KB Output is correct
3 Correct 7 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 5 ms 336 KB Output is correct
6 Correct 49 ms 336 KB Output is correct
7 Correct 7 ms 336 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 10832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 10684 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 10680 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 277 ms 16676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 118 ms 10692 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 386 ms 22960 KB Output isn't correct
2 Halted 0 ms 0 KB -