Submission #394128

#	Time	Username	Problem	Language	Result	Execution time	Memory
394128		Lobo	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	568 ms	20776 KiB

bobek

#include <bits/stdc++.h>
 
using namespace std;

const long long INFll =  1000000000000000000;
const int INFii = 1000000000;
const long long mod = (long long) 1e9 + 7;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define S second
#define F first
#define MP make_pair
#define PB push_back

#define maxn 

ll n, m, n1, n2, ans;
vector<ll> a1, a2, l1, l2;

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

    //freopen("in.in", "r", stdin);
    //freopen("____.out", "w", stdout);

    cin >> n >> m;

    n2 = n/2;
    n1 = n - n2;
    
    for(ll i = 0; i < n1; i++) {
        ll c;
        cin >> c;
        a1.PB(c);
    }

    for(ll i = 0; i < n1; i++) {
        ll c;
        cin >> c;
        a2.PB(c);
    }


    for(ll mask = 0; mask < (1<<n1); mask++) {
        ll sum = 0;

        for(ll i = 0; i < n1; i++)
            if((mask&(1<<i)) != 0)
                sum+= a1[i];
            
        l1.PB(sum);
    }

    for(ll mask = 0; mask < (1<<n2); mask++) {
        ll sum = 0;

        for(ll i = 0; i < n2; i++)
            if((mask&(1<<i)) != 0)
                sum+= a2[i];
            
        l2.PB(sum);
    }

    sort(l2.begin(),l2.end());

    for(auto a : l1) {
        ans+= upper_bound(l2.begin(),l2.end(),m-a) - l2.begin();
    }

    cout << ans << endl;
    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