Submission #572622

#	Time	Username	Problem	Language	Result	Execution time	Memory
572622		vladislav11	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	333 ms	21032 KiB

bobek

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n;
ll m;
vector<ll> a;

void f ( vector<ll> &x, vector<ll> &v )
{
    int m = x.size();

    for ( int i=0; i < (1<<m); i++ )
    {
        ll sum = 0;

        for ( int j=0; j<m; j++ )
        if ( (i>>j) & 1 )
            sum += x[j];

        v.push_back( sum );
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    a.resize(n);

    for ( auto& el : a )
        cin >> el;

    vector<ll> x, y;

    {
        int m = n/2;

        for ( int i=0; i<m; i++ )
            x.push_back( a[i] );

        for ( int i=m; i<n; i++ )
            y.push_back( a[i] );
    }

    vector<ll> p, q;

    f( x, p );
    f( y, q );

    sort( p.begin(), p.end() );
    sort( q.begin(), q.end() );

    ll ans = 0;

    for ( auto& el : q )
    {
        ll w = m - el;

        int l = -1, r = int(p.size())-1;

        while ( l < r )
        {
            int mid = ( l + r + 1 ) / 2;

            if ( p[mid] <= w )
                l = mid;
            else
                r = mid-1;
        }

        ans += l+1;
    }

    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