Submission #441567

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
441567	2021-07-05T11:33:24 Z	dynam1c	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	531 ms	8524 KB

bobek

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define endl "\n"
#define all(c) (c).begin(),(c).end()

// when you ponder, divide and conquer

signed main() {
	// freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	ll m;
	cin >> n >> m;
	vector<ll> arr(n);
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	vector<ll> ee(1<<(n/2));
	for (int b = 0; b < 1<<(n/2); b++) {
		ll x = 0;
		for (int l = 0; l < 20; l++) if (b>>l & 1)
			x += arr[l];
		ee[b] = x;
	}
	sort(all(ee));
	ll res = 0;
	for (int b = 0; b < 1<<(n-n/2); b++) {
		ll x = 0;
		for (int l = 0; l < 20; l++) if (b>>l & 1)
			x += arr[n/2+l];
		res += upper_bound(all(ee), m-x) - ee.begin();
	}
	cout << res << endl;
}
/* --- PSolving ---
 * Simplifying (getting rid of variables, conditions, code logic, etc.)
 * Reframing
 * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.)
 * Inducing
 * Divide and conquer
 * Working backwards
 * Visual intuition
 * !! Reductions don't have to be specializations, they can be generalizations
 */

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	0 ms	204 KB	Output is correct
3	Correct	1 ms	308 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	316 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	0 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	1 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	1 ms	248 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	0 ms	204 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	824 KB	Output is correct
2	Correct	104 ms	2252 KB	Output is correct
3	Correct	515 ms	8524 KB	Output is correct
4	Correct	103 ms	2252 KB	Output is correct
5	Correct	17 ms	716 KB	Output is correct
6	Correct	7 ms	460 KB	Output is correct
7	Correct	15 ms	780 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	1228 KB	Output is correct
2	Correct	35 ms	716 KB	Output is correct
3	Correct	198 ms	4424 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	8 ms	460 KB	Output is correct
6	Correct	15 ms	716 KB	Output is correct
7	Correct	15 ms	716 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	73 ms	1228 KB	Output is correct
2	Correct	171 ms	2252 KB	Output is correct
3	Correct	160 ms	2252 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	96 ms	2252 KB	Output is correct
6	Correct	245 ms	8524 KB	Output is correct
7	Correct	84 ms	2252 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	4300 KB	Output is correct
2	Correct	31 ms	716 KB	Output is correct
3	Correct	11 ms	460 KB	Output is correct
4	Correct	0 ms	204 KB	Output is correct
5	Correct	8 ms	588 KB	Output is correct
6	Correct	178 ms	4300 KB	Output is correct
7	Correct	14 ms	716 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	716 KB	Output is correct
2	Correct	98 ms	2252 KB	Output is correct
3	Correct	9 ms	460 KB	Output is correct
4	Correct	10 ms	460 KB	Output is correct
5	Correct	116 ms	2380 KB	Output is correct
6	Correct	20 ms	716 KB	Output is correct
7	Correct	256 ms	8524 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	398 ms	8524 KB	Output is correct
2	Correct	34 ms	716 KB	Output is correct
3	Correct	11 ms	460 KB	Output is correct
4	Correct	531 ms	8524 KB	Output is correct
5	Correct	140 ms	4428 KB	Output is correct
6	Correct	15 ms	824 KB	Output is correct
7	Correct	30 ms	1228 KB	Output is correct

Submission #441567

Compilation message