Submission #542957

#	Time	Username	Problem	Language	Result	Execution time	Memory
542957		prvocislo	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	460 ms	8684 KiB

bobek

#include <algorithm>
#include <iostream>
#include <string>
#include <chrono>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>
#include <random>
#include <map>
#include <set>
typedef long long ll;
typedef long double ld;
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll s;
    cin >> n >> s;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    int n1 = n / 2, n2 = n - n / 2;
    vector<ll> s1;
    for (int i = 0; i < (1 << n1); i++)
    {
        ll sum = 0;
        for (int j = 0; j < n1; j++) if (i & (1 << j)) sum += a[j];
        s1.push_back(sum);
    }
    sort(s1.begin(), s1.end());
    ll ans = 0;
    for (int i = 0; i < (1 << n2); i++)
    {
        ll sum = 0;
        for (int j = 0; j < n2; j++) if (i & (1 << j)) sum += a[n1 + j];
        ans += upper_bound(s1.begin(), s1.end(), s - sum) - s1.begin();
    }
    cout << ans << "\n";
    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