Submission #492703

#	Time	Username	Problem	Language	Result	Execution time	Memory
492703		zhougz	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	440 ms	8516 KiB

bobek

/**
 *    author: zhougz
 *    created: 08/12/2021 14:48:56
**/
#include <bits/stdc++.h>

using namespace std;

// Man-in-the-middle attack again?
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	long long m;
	cin >> n >> m;
	vector<long long> arr;
	arr.reserve(n);
	for (int i = 0; i < n; i++) {
		long long x;
		cin >> x;
		if (x <= m) {
			arr.push_back(x);
		}
	}
	n = arr.size();
	vector<long long> v;
	const int c1 = (n + 1) / 2, c2 = n / 2;
	assert(c1 + c2 == n);
	v.reserve(1 << c1);
	for (int i = 0; i < (1 << c1); i++) {
		long long cur = 0;
		for (int j = 0; j < c1; j++) {
			if ((i >> j) & 1) {
				cur += arr[j];
				if (cur > m) {
					goto end;
				}
			}
		}
		v.push_back(cur);
		end:;
	}
	sort(v.begin(), v.end());
	long long res = 0;
	for (int i = 0; i < (1 << c2); i++) {
		long long cur = 0;
		for (int j = 0; j < c2; j++) {
			if ((i >> j) & 1) {
				cur += arr[c1 + j];
				if (cur > m) {
					goto end2;
				}
			}
		}
		res += upper_bound(v.begin(), v.end(), m - cur) - v.begin();
		end2:;
	}
	cout << res;
	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