oj.uz

Submission #954450

# Submission time Handle Problem Language Result Execution time Memory
954450 2024-03-28T00:09:52 Z thiago_bastos Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 289 ms 17124 KB 
#include <bits/stdc++.h>

using namespace std;

auto split(vector<int64_t> a) {
    int n = a.size();
    vector<int64_t> first(a.begin(), a.begin() + (n + 1) / 2);
    vector<int64_t> second(a.begin() + (n + 1) / 2, a.end());
    return make_pair(first, second);
}

vector<int64_t> generateSubsets(vector<int64_t>& a) {
    int n = a.size();
    vector<int64_t> subset(1 << n);
    for(int i = 0; i < (1 << n); ++i) {
        subset[i] = 0;
        for(int j = 0; j < n; ++j) {
            if(i & (1 << j))
                subset[i] += a[j];
        }
    }
    return subset;
}

void solve() {
    int n;
    int64_t m, answer {};

    cin >> n >> m;

    vector<int64_t> a(n);

    for(auto& v : a) cin >> v;

    auto [p, q] = split(a);

    auto pSubset = generateSubsets(p);
    auto qSubset = generateSubsets(q);

    sort(pSubset.begin(), pSubset.end());
    sort(qSubset.begin(), qSubset.end());

    int hi = qSubset.size();
    
    for(auto sum : pSubset) {
        while(hi > 0 && sum + qSubset[hi - 1] > m) --hi;
        answer += hi;
    }

    cout << answer << '\n';
}

int main() {
    int t = 1;
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    //cin >> t;
    while(t--) solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
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 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 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1884 KB Output is correct
2 Correct 67 ms 4572 KB Output is correct
3 Correct 289 ms 17124 KB Output is correct
4 Correct 66 ms 4444 KB Output is correct
5 Correct 12 ms 1368 KB Output is correct
6 Correct 7 ms 1112 KB Output is correct
7 Correct 15 ms 1372 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2392 KB Output is correct
2 Correct 24 ms 1884 KB Output is correct
3 Correct 120 ms 8784 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 15 ms 1496 KB Output is correct
7 Correct 15 ms 1372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3548 KB Output is correct
2 Correct 100 ms 6612 KB Output is correct
3 Correct 100 ms 6492 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 71 ms 6616 KB Output is correct
6 Correct 256 ms 16724 KB Output is correct
7 Correct 99 ms 6484 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 12748 KB Output is correct
2 Correct 23 ms 1884 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 205 ms 12512 KB Output is correct
7 Correct 16 ms 1368 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 1880 KB Output is correct
2 Correct 65 ms 4440 KB Output is correct
3 Correct 7 ms 860 KB Output is correct
4 Correct 8 ms 856 KB Output is correct
5 Correct 75 ms 6492 KB Output is correct
6 Correct 23 ms 2136 KB Output is correct
7 Correct 272 ms 16848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 17104 KB Output is correct
2 Correct 24 ms 1880 KB Output is correct
3 Correct 8 ms 860 KB Output is correct
4 Correct 286 ms 16864 KB Output is correct
5 Correct 100 ms 8788 KB Output is correct
6 Correct 15 ms 1372 KB Output is correct
7 Correct 31 ms 2396 KB Output is correct