oj.uz

Submission #492703

# Submission time Handle Problem Language Result Execution time Memory
492703 2021-12-08T13:02:27 Z zhougz Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 440 ms 8516 KB 
/**
 *    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.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1260 KB Output is correct
2 Correct 91 ms 2372 KB Output is correct
3 Correct 440 ms 8416 KB Output is correct
4 Correct 92 ms 2252 KB Output is correct
5 Correct 14 ms 716 KB Output is correct
6 Correct 6 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1348 KB Output is correct
2 Correct 32 ms 1284 KB Output is correct
3 Correct 226 ms 4364 KB Output is correct
4 Correct 0 ms 316 KB Output is correct
5 Correct 6 ms 564 KB Output is correct
6 Correct 14 ms 844 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 2292 KB Output is correct
2 Correct 150 ms 4376 KB Output is correct
3 Correct 143 ms 4300 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 83 ms 4324 KB Output is correct
6 Correct 246 ms 8516 KB Output is correct
7 Correct 0 ms 204 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 8412 KB Output is correct
2 Correct 29 ms 1228 KB Output is correct
3 Correct 10 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 8 ms 476 KB Output is correct
6 Correct 189 ms 8432 KB Output is correct
7 Correct 1 ms 320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1228 KB Output is correct
2 Correct 87 ms 2360 KB Output is correct
3 Correct 8 ms 460 KB Output is correct
4 Correct 9 ms 460 KB Output is correct
5 Correct 92 ms 4284 KB Output is correct
6 Correct 23 ms 1228 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 8400 KB Output is correct
2 Correct 30 ms 1228 KB Output is correct
3 Correct 9 ms 460 KB Output is correct
4 Correct 421 ms 8384 KB Output is correct
5 Correct 131 ms 4340 KB Output is correct
6 Correct 13 ms 716 KB Output is correct
7 Correct 0 ms 204 KB Output is correct