Submission #208154

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208154	2020-03-10T06:32:50 Z	smhh22	Ice Hockey World Championship (CEOI15_bobek)	C++11	100 / 100	414 ms	16848 KB

bobek

//besmellah
#include <bits/stdc++.h>
using namespace std;

#define int long long
int sum[1 << 20], a[40];
vector <int> V;

int32_t main() {
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	V.push_back(0);
	for (int mask = 1; mask < (1 << (n / 2)); mask++) {
		sum[mask] = sum[mask - (mask & -mask)] + a[__builtin_ctz(mask)];
		V.push_back(sum[mask]);
	}
	sort(V.begin(), V.end());
	int ans = 0;
	ans += upper_bound(V.begin(), V.end(), m) - V.begin();
	for (int mask = 1; mask < (1 << ((n + 1) / 2)); mask++) {
		sum[mask] = sum[mask - (mask & -mask)] + a[n / 2 + __builtin_ctz(mask)];
		ans += upper_bound(V.begin(), V.end(), m - sum[mask]) - V.begin();
	}
	cout << ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	26 ms	2032 KB	Output is correct
2	Correct	79 ms	4580 KB	Output is correct
3	Correct	394 ms	16848 KB	Output is correct
4	Correct	76 ms	4580 KB	Output is correct
5	Correct	12 ms	1516 KB	Output is correct
6	Correct	8 ms	1012 KB	Output is correct
7	Correct	12 ms	1516 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	34 ms	2536 KB	Output is correct
2	Correct	29 ms	2032 KB	Output is correct
3	Correct	146 ms	8668 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	7 ms	1012 KB	Output is correct
6	Correct	13 ms	1520 KB	Output is correct
7	Correct	12 ms	1516 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	56 ms	3564 KB	Output is correct
2	Correct	133 ms	6628 KB	Output is correct
3	Correct	122 ms	6672 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	44 ms	6628 KB	Output is correct
6	Correct	133 ms	16848 KB	Output is correct
7	Correct	43 ms	6628 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	279 ms	12816 KB	Output is correct
2	Correct	24 ms	2028 KB	Output is correct
3	Correct	11 ms	1012 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	8 ms	1012 KB	Output is correct
6	Correct	103 ms	12764 KB	Output is correct
7	Correct	11 ms	1520 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	27 ms	2028 KB	Output is correct
2	Correct	74 ms	4580 KB	Output is correct
3	Correct	10 ms	1012 KB	Output is correct
4	Correct	12 ms	1012 KB	Output is correct
5	Correct	63 ms	6628 KB	Output is correct
6	Correct	13 ms	2032 KB	Output is correct
7	Correct	141 ms	16848 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	286 ms	16848 KB	Output is correct
2	Correct	29 ms	2032 KB	Output is correct
3	Correct	11 ms	1012 KB	Output is correct
4	Correct	414 ms	16848 KB	Output is correct
5	Correct	64 ms	8668 KB	Output is correct
6	Correct	13 ms	1520 KB	Output is correct
7	Correct	20 ms	2536 KB	Output is correct

Submission #208154

Compilation message