Submission #436340

#	Time	Username	Problem	Language	Result	Execution time	Memory
436340		iulia13	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	351 ms	16836 KiB

bobek

#include <bits/stdc++.h>

using namespace std;
const int N = 2e6 + 6;
#define ll long long
map <ll, ll> cate;
map <ll, ll> dp;
set <ll> s;
ll v[N];
ll a[N], b[N];

int main()
{
    ll n, m, nr, i, h, j, na, nb;
    cin >> n >> m;
    for (i = 0; i < n; i++)
        cin >> v[i];
    h = n / 2;
    for (i = 0; i < (1 << h); i++)
    {
        for (j = 0; j < h; j++)
            if (i & (1 << j))
                a[i] += v[j];
    }
    na = (1 << h);
    sort(a, a + na);
    for (i = h; i < n; i++)
        v[i - h] = v[i];

    h = n - h;
    for (i = 0; i < (1 << h); i++)
    {
        for (j = 0; j < h; j++)
            if (i & (1 << j))
                b[i] += v[j];
    }
    nb = (1 << h);
    sort(b, b + nb);
    na--;
    nb--;
    j = nb;
    ll ans = 0;
    for (i = 0; i <= na; i++)
    {
        while (b[j] + a[i] > m && j > -1)
            j--;
        ans += (j + 1);
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:14:14: warning: unused variable 'nr' [-Wunused-variable]
   14 |     ll n, m, nr, i, h, j, na, nb;
      |              ^~

• 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