Submission #74555

#	Time	Username	Problem	Language	Result	Execution time	Memory
74555		xennygrimmato	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	471 ms	17100 KiB

bobek

#include <iostream>
#include <algorithm>
#include <climits>
#define ll long long
using namespace std;

const ll N = 41;

ll n, k;
ll a[N];
ll f1[1<<20], f2[1<<20];

void compute_costs(int L, int R, ll* arr) {
	// [L, R)
	for(ll i = 1 ; i < (1 << (R - L)) ; i++) {
		ll cost = 0;
		for(ll j = 0 ; j < 20 ; ++j) {
			if(i & (1 << j)) {
				cost += a[L + j];
				if(cost > k) {
					cost = 4e18;
					break;
				}
			}
		}
		arr[i] = cost;
	}
	sort(arr, arr + (1 << (R - L)));

	// for(int i = 0 ; i < 1 << (R - L) ; i++) {
	// 	cout << arr[i] << " ";
	// }
	// cout << "\n";
}

void solve() {
	// brute for first half
	compute_costs(0, n / 2, f1);
	// for 2nd half
	compute_costs(n / 2, n, f2);
	// combine
	ll ans = 0;
	int L = n / 2, R = n;
	int end_idx = 1 << (R - L);
	for(ll i = 0 ; i < (1 << (n / 2)) ; i++) {
		ll bound = k - f1[i];
		if(bound <= 0) continue;
		ans += max(0, (int)(upper_bound(f2, f2 + (end_idx), bound) - f2) - 1);
		// cout << ans << "\n";
	}
	ans += max(0, (int)(upper_bound(f1, f1 + (1 << (n / 2)), k) - f1) - 1);
	cout << ans + 1 << "\n";
}

int main() {
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++) {
		cin >> a[i];
	}
	solve();
}

• 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