Submission #648242

#	Time	Username	Problem	Language	Result	Execution time	Memory
648242		ymm	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	374 ms	16716 KiB

bobek

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10