Submission #1218632

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218632		giorgi123glm	Ice Hockey World Championship (CEOI15_bobek)	C++20	80 / 100	1099 ms	82484 KiB

bobek

#include <algorithm>
#include <functional>
#include <iostream>
#include <fstream>
#include <list>
#include <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];

    map <int, int> m;
    for (int bit = 0; bit < (1 << (N / 2)); bit++) {
        int sum = 0;
        for (int i = 0; i < 20; i++)
            if (bit & (1 << i))
                sum += v[i + 1];
        m[sum]++;
    }

    vector <pair <int, int> > m1 = {{-1e18, 0}};
    m1.reserve (m.size() + 10);
    for (const pair <int, int>& e : m)
        m1.push_back (e);
    for (int i = 2; i < m1.size(); i++)
        m1[i].second += m1[i - 1].second;

    int ans = 0;
    for (int bit = 0; bit < (1 << (N - N / 2)); bit++) {
        int sum = 0;
        for (int i = 0; i < 20; i++)
            if (bit & (1 << i))
                sum += v[i + N / 2 + 1];
        auto it = lower_bound (m1.begin(), m1.end(), (pair <int, int>){(M - sum) + 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: 0 / 10
• Subtask 10: 0 / 10