oj.uz

Submission #259227

# Submission time Handle Problem Language Result Execution time Memory
259227 2020-08-07T12:33:41 Z vioalbert Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 293 ms 33476 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N = 45, MAX = 20;
ll n, m, border;
ll a[N];
ll dp1[(1<<MAX)], dp2[(1<<MAX)];
vector<ll> v1, v2;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	border = (n+1)/2;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a+n, greater<ll>());

	for(int i = 0; i < border; i++)
		dp1[(1<<i)] = a[i];
	dp1[0] = 0;

	for(ll mask = 0; mask < (1<<border); mask++) {
		if(__builtin_popcount(mask) > 1) {
			int x = mask&(-mask);
			dp1[mask] = dp1[x] + dp1[mask^x];
		}
		if(dp1[mask] <= m) {
			v1.push_back(dp1[mask]);
		}
	
	}

	for(int i = border; i < n; i++)
		dp2[(1<<(i-border))] = a[i];
	dp2[0] = 0;

	for(ll mask = 0; mask < (1<<(n-border)); mask++) {
		if(__builtin_popcount(mask) > 1) {
			int x = mask&(-mask);
			dp2[mask] = dp2[x] + dp2[mask^x];
		}
		if(dp2[mask] <= m) {
			v2.push_back(dp2[mask]);
		}
	}

	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());

	ll ans = 0;
	for(ll x : v1) {
		ll len = upper_bound(v2.begin(), v2.end(), m - x) - v2.begin();
		ans += len;
	}
	cout << ans << '\n';

	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3960 KB Output is correct
2 Correct 67 ms 8436 KB Output is correct
3 Correct 293 ms 32508 KB Output is correct
4 Correct 64 ms 8492 KB Output is correct
5 Correct 8 ms 2428 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 1 ms 1536 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 4632 KB Output is correct
2 Correct 22 ms 3960 KB Output is correct
3 Correct 100 ms 16856 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 6 ms 1532 KB Output is correct
6 Correct 13 ms 2556 KB Output is correct
7 Correct 2 ms 1408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7284 KB Output is correct
2 Correct 96 ms 14448 KB Output is correct
3 Correct 103 ms 14320 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 55 ms 14704 KB Output is correct
6 Correct 230 ms 33476 KB Output is correct
7 Correct 7 ms 6528 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 28652 KB Output is correct
2 Correct 25 ms 3960 KB Output is correct
3 Correct 8 ms 1532 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 5 ms 1532 KB Output is correct
6 Correct 209 ms 29164 KB Output is correct
7 Correct 1 ms 1408 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3960 KB Output is correct
2 Correct 65 ms 8668 KB Output is correct
3 Correct 7 ms 1532 KB Output is correct
4 Correct 7 ms 1404 KB Output is correct
5 Correct 50 ms 13936 KB Output is correct
6 Correct 21 ms 3960 KB Output is correct
7 Correct 18 ms 16768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 275 ms 33252 KB Output is correct
2 Correct 22 ms 3832 KB Output is correct
3 Correct 8 ms 1532 KB Output is correct
4 Correct 269 ms 32708 KB Output is correct
5 Correct 72 ms 16880 KB Output is correct
6 Correct 14 ms 2556 KB Output is correct
7 Correct 3 ms 2432 KB Output is correct