Submission #1248931

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248931		Jovica	Ice Hockey World Championship (CEOI15_bobek)	C++20	100 / 100	293 ms	20892 KiB

bobek

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
int n;
ll m;
vector<ll> v;
vector<ll> op1,op2;

void f1(int p,ll z)
{
    if (p == n/2){
        op1.push_back(z);
        return;
    }
    f1(p+1,z);
    f1(p+1,z+v[p]);
}

void f2(int p,ll z)
{
    if (p == n){
        op2.push_back(z);
        return;
    }
    f2(p+1,z);
    f2(p+1,z+v[p]);
}

int main()
{
    cin>>n>>m;v.resize(n);

    for (int i=0;i<n;i++) cin>>v[i];

    if (n == 1){
        if (m >= v[0]) cout<<2;
        else cout<<1;
        return 0;
    }

    f1(0,0);
    f2(n/2,0);

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

    ll odg = 0;
    for (auto x: op1)
    {
        ll p = upper_bound(op2.begin(),op2.end(),m-x) - op2.begin();
        odg += p;
        //cout<<"za "<<x<<" dodava "<<p<<endl;
    }

    cout<<odg<<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