Submission #1218638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218638		giorgi123glm	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	773 ms	260992 KiB

bobek

#include <algorithm>
#include <functional>
#include <iostream>
#include <fstream>
#include <list>
#include <unordered_map>
using namespace std;

#define int long long

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0, M = 0;
    cin >> N >> M;

    vector <int> v (N + 1);
    for (int i = 1; i <= N; i++)
        cin >> v[i];
    unordered_map <int, int> m (1e7);
    vector <int> bit_sum1 (1 << 20);
    m[0]++;
    for (int bit = 1; bit < (1 << (N / 2)); bit++) {
        const int bit_ind = 31 - __builtin_clz (bit);
        bit_sum1[bit] = bit_sum1[bit ^ (1 << bit_ind)] + v[bit_ind + 1];
        m[bit_sum1[bit]]++;
    }
    vector <pair <int, int> > m1 = {{-1e18, 0}};
    m1.reserve (m.size() + 10);
    for (const pair <int, int>& e : m)
        m1.push_back (e);
    sort (m1.begin(), m1.end());
    for (int i = 2; i < m1.size(); i++)
        m1[i].second += m1[i - 1].second;
    vector <int> bit_sum2 (1 << 20);
    unordered_map <int, int> m2 (1e7);
    m2[0]++;
    for (int bit = 1; bit < (1 << (N - N / 2)); bit++) {
        const int bit_ind = 31 - __builtin_clz (bit);
        bit_sum2[bit] = bit_sum2[bit ^ (1 << bit_ind)] + v[bit_ind + 1 + N / 2];
        m2[bit_sum2[bit]]++;
    }
    int ans = 0;
    for (const pair <int, int>& e : m2) {
        auto it = lower_bound (m1.begin(), m1.end(), (pair <int, int>){(M - e.first) + 1, 0});
        ans += (--it)->second * e.second;
    }

    cout << ans << '\n';
}

• 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