답안 #74555 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74555	2018-09-03T13:39:08 Z	xennygrimmato	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	471 ms	17100 KB

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	256 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	500 KB	Output is correct
2	Correct	2 ms	500 KB	Output is correct
3	Correct	2 ms	500 KB	Output is correct
4	Correct	2 ms	628 KB	Output is correct
5	Correct	2 ms	628 KB	Output is correct
6	Correct	2 ms	628 KB	Output is correct
7	Correct	2 ms	632 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	632 KB	Output is correct
2	Correct	2 ms	688 KB	Output is correct
3	Correct	2 ms	688 KB	Output is correct
4	Correct	2 ms	688 KB	Output is correct
5	Correct	2 ms	688 KB	Output is correct
6	Correct	2 ms	688 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	688 KB	Output is correct
2	Correct	2 ms	688 KB	Output is correct
3	Correct	2 ms	688 KB	Output is correct
4	Correct	3 ms	688 KB	Output is correct
5	Correct	2 ms	688 KB	Output is correct
6	Correct	2 ms	688 KB	Output is correct
7	Correct	2 ms	688 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	2220 KB	Output is correct
2	Correct	116 ms	4688 KB	Output is correct
3	Correct	471 ms	16940 KB	Output is correct
4	Correct	111 ms	16940 KB	Output is correct
5	Correct	21 ms	16940 KB	Output is correct
6	Correct	14 ms	16940 KB	Output is correct
7	Correct	6 ms	16940 KB	Output is correct

Subtask #6
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	52 ms	16940 KB	Output is correct
2	Correct	39 ms	16940 KB	Output is correct
3	Correct	190 ms	16940 KB	Output is correct
4	Correct	2 ms	16940 KB	Output is correct
5	Correct	11 ms	16940 KB	Output is correct
6	Correct	26 ms	16940 KB	Output is correct
7	Correct	5 ms	16940 KB	Output is correct

Subtask #7
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	81 ms	16940 KB	Output is correct
2	Correct	155 ms	16940 KB	Output is correct
3	Correct	162 ms	16940 KB	Output is correct
4	Correct	2 ms	16940 KB	Output is correct
5	Correct	113 ms	16940 KB	Output is correct
6	Correct	403 ms	17016 KB	Output is correct
7	Correct	22 ms	17016 KB	Output is correct

Subtask #8
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	324 ms	17016 KB	Output is correct
2	Correct	38 ms	17016 KB	Output is correct
3	Correct	14 ms	17016 KB	Output is correct
4	Correct	2 ms	17016 KB	Output is correct
5	Correct	12 ms	17016 KB	Output is correct
6	Correct	335 ms	17016 KB	Output is correct
7	Correct	5 ms	17016 KB	Output is correct

Subtask #9
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	38 ms	17016 KB	Output is correct
2	Correct	107 ms	17016 KB	Output is correct
3	Correct	14 ms	17016 KB	Output is correct
4	Correct	13 ms	17016 KB	Output is correct
5	Correct	114 ms	17016 KB	Output is correct
6	Correct	37 ms	17016 KB	Output is correct
7	Correct	59 ms	17020 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	458 ms	17100 KB	Output is correct
2	Correct	40 ms	17100 KB	Output is correct
3	Correct	14 ms	17100 KB	Output is correct
4	Correct	461 ms	17100 KB	Output is correct
5	Correct	161 ms	17100 KB	Output is correct
6	Correct	27 ms	17100 KB	Output is correct
7	Correct	8 ms	17100 KB	Output is correct

답안 #74555

Compilation message