Submission #184112

#	Time	Username	Problem	Language	Result	Execution time	Memory
184112		nicolaalexandra	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	536 ms	8580 KiB

bobek

#include <bits/stdc++.h>
#define DIMN 50
#define DIMM 2000000
using namespace std;
long long v[DIMN],d[DIMM];
long long m;
int n,i,k;
int main (){

    cin>>n>>m;
    for (i=1;i<=n;i++)
        cin>>v[i];

    /// iau toate mastile din prima jumatate
    int val = n/2;
    for (long long mask=0;mask<(1<<val);mask++){
        long long sum = 0;
        for (int bit=0;bit<val;bit++)
            if (mask&(1<<bit))
                sum += v[bit+1];
        if (sum <= m)
            d[++k] = sum;
    }
    sort (d+1,d+k+1);
    val = n - n/2;
    long long ans = 0;
    for (long long mask=0;mask<(1<<val);mask++){
        long long sum = 0;
        for (int bit=0;bit<val;bit++)
            if (mask&(1<<bit))
                sum += v[n/2+bit+1];
        if (sum > m)
            continue;
        long long dif = m - sum;
        int st = 1, dr = k, sol = 0;
        while (st <= dr){
            int mid = (st+dr)>>1;
            if (d[mid] <= dif){
                sol = mid;
                st = mid+1;
            } else dr = mid-1;
        }
        ans += sol;
    }
    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