Submission #99779

#	Time	Username	Problem	Language	Result	Execution time	Memory
99779		HardNut	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	562 ms	8784 KiB

bobek

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e4 + 5;
const ll INF = 1e18 + 5;
const ll mod = 1e6 + 7;
const int tx[] = {1, -1, 0, 0}, ty[] = {0, 0, 1, -1};
const ll bs = 31;

int n;
ll m;
ll a[45], ans;
vector <ll> vec;

main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int nn = n / 2;
    for (int mask = 0; mask < (1 << nn); mask++) {
        ll res = 0;
        for (int i = 0; i < nn; i++) {
            if ((mask >> i) & 1) {
                res += a[i + 1];
            }
        }
        vec.push_back(res);
    }
    sort(vec.begin(), vec.end());
    for (int mask = 0; mask < (1 << (n - nn)); mask++) {
        ll res = 0;
        for (int i = 0; i < n - nn; i++) {
            if ((mask >> i) & 1) {
                res += a[i + nn + 1];
            }
        }
        ll it = upper_bound(vec.begin(), vec.end(), m - res) - vec.begin();
        ans += it;
    }
    cout << ans;
    return 0;
}
/**
5
1 2 1 1 1
*/

Compilation message (stderr)

bobek.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^

• 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