oj.uz

Submission #648242

# Submission time Handle Problem Language Result Execution time Memory
648242 2022-10-05T19:41:37 Z ymm Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 374 ms 16716 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;

const int N = 40, M = 20;
ll a[N];
ll mim[1<<M];
ll sum2[1<<M];
ll bud;
int n;

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> n >> bud;
	Loop (i,0,n)
		cin >> a[i];
	int m = n/2;
	Loop (msk,1,1<<m) {
		int i = __builtin_ctz(msk);
		mim[msk] = mim[msk ^ (1<<i)] + a[i];
	}
	sort(mim, mim + (1<<m));
	ll ans = upper_bound(mim, mim+(1<<m), bud) - mim;
	Loop (msk,1,1<<(n-m)) {
		int i = __builtin_ctz(msk);
		sum2[msk] = sum2[msk ^ (1<<i)] + a[i + m];
		ans += upper_bound(mim, mim+(1<<m), bud-sum2[msk]) - mim;
	}
	cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1732 KB Output is correct
2 Correct 70 ms 4304 KB Output is correct
3 Correct 374 ms 16632 KB Output is correct
4 Correct 76 ms 4416 KB Output is correct
5 Correct 8 ms 1348 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 8 ms 1372 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2292 KB Output is correct
2 Correct 24 ms 1860 KB Output is correct
3 Correct 142 ms 8532 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 8 ms 1352 KB Output is correct
7 Correct 7 ms 1364 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 3332 KB Output is correct
2 Correct 128 ms 6500 KB Output is correct
3 Correct 105 ms 6348 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 45 ms 6444 KB Output is correct
6 Correct 106 ms 16716 KB Output is correct
7 Correct 45 ms 6488 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 257 ms 12540 KB Output is correct
2 Correct 19 ms 1880 KB Output is correct
3 Correct 6 ms 852 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 5 ms 852 KB Output is correct
6 Correct 75 ms 12532 KB Output is correct
7 Correct 7 ms 1372 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 1876 KB Output is correct
2 Correct 69 ms 4296 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 8 ms 856 KB Output is correct
5 Correct 54 ms 6452 KB Output is correct
6 Correct 11 ms 1876 KB Output is correct
7 Correct 143 ms 16612 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 16648 KB Output is correct
2 Correct 25 ms 1752 KB Output is correct
3 Correct 6 ms 864 KB Output is correct
4 Correct 346 ms 16616 KB Output is correct
5 Correct 60 ms 8448 KB Output is correct
6 Correct 8 ms 1276 KB Output is correct
7 Correct 14 ms 2376 KB Output is correct