oj.uz

Submission #74555

# Submission time Handle Problem Language Result Execution time Memory
74555 2018-09-03T13:39:08 Z xennygrimmato Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 471 ms 17100 KB 
#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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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