Submission #954450

#	Time	Username	Problem	Language	Result	Execution time	Memory
954450		thiago_bastos	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	289 ms	17124 KiB

bobek

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10