Submission #760766

#	Time	Username	Problem	Language	Result	Execution time	Memory
760766		BidoTeima	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	429 ms	8648 KiB

bobek

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
int mod = 1e9 + 7;
int main()
{ 
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    int n;
    ll m;
    cin>>n>>m;
    ll a[n];
    for(int i = 0; i < n; i++)cin>>a[i];
    // [0, n / 2 - 1], [n / 2, n - 1]
    vector<ll>v;
    for(int mask = 0; mask < (1 << ((n+1)>>1)); mask++){
        ll sum = 0;
        for(int i = 0; i < (n+1)/2; i++){
            if(mask & (1 << i))
                sum += a[i + (n >> 1)];
        }
        v.push_back(sum);
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for(int mask = 0; mask < (1 << (n >> 1)); mask++){
        ll sum = 0;
        for(int i = 0; i < (n >> 1); i++){
            if(mask & (1 << i))
                sum += a[i];
        }
        ans += upper_bound(v.begin(), v.end(), m - sum) - v.begin();
    }
    cout<<ans;
    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