제출 #1218635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1218635		giorgi123glm	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	522 ms	77428 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;
    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);
    int ans = (--lower_bound (m1.begin(), m1.end(), (pair <int, int>){M + 1, 0}))->second;
    
    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];

        auto it = lower_bound (m1.begin(), m1.end(), (pair <int, int>){(M - bit_sum2[bit]) + 1, 0});
        ans += (--it)->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