Submission #108374

#	Time	Username	Problem	Language	Result	Execution time	Memory
108374		luciocf	Ice Hockey World Championship (CEOI15_bobek)	C++14	0 / 100	732 ms	49496 KiB

bobek

#include <bits/stdc++.h>

using namespace std;

const int maxn = 40;

typedef long long ll;

struct node
{
	node *l, *r;

	ll v;
	int w, sz;

	node(ll vv)
	{
		v = vv, w = rand();
		l = r = NULL;
	}
};

typedef node*& node_t;

int sz(node *t)
{
	return (t ? t->sz : 0);
}

void op(node *t)
{
	if (t) t->sz = sz(t->l)+sz(t->r)+1;
}

void split(node *t, node_t l, node_t r, ll v)
{
	if (!t) return void(l=r=NULL);

	if (t->v > v) split(t->l, l, t->l, v), r = t;
	else split(t->r, t->r, r, v), l = t;

	op(t);
}

void merge(node_t t, node *l, node *r)
{
	if (!l || !r) t = (l ? l : r);
	else if (l->w > r->w) merge(l->r, l->r, r), t = l;
	else merge(r->l, l, r->l), t = r;

	op(t);
}

void insert(node_t t, node *aux)
{
	if (!t) t = aux;
	else if (aux->w > t->w) split(t, aux->l, aux->r, t->v), t = aux;
	else insert((aux->v > t->v ? t->r : t->l), aux);

	op(t);
}

int get(node *t, ll v)
{
	if (!t) return 0;

	if (t->v <= v) return sz(t->l)+get(t->r, v);
	return get(t->l, v);
}

ll a[maxn];

int main(void)
{
	int n;
	ll m;

	scanf("%d %lld", &n, &m);

	for (int i = 0; i < n; i++)
		scanf("%lld", &a[i]);

	int mid = n/2;
	ll ans = 0;

	node *t = NULL;

	for (int mask = 0; mask < (1<<mid); mask++)
	{
		ll sum = 0;
		for (int i = 0; i <= mid; i++)
			if (mask&(1<<i))
				sum += a[i];

		if (sum <= m)
		{
			ans++;
			
			node *aux = new node(sum);
			insert(t, aux);
		}
	}

	int k = n-mid;

	for (int mask = 0; mask < (1<<k); mask++)
	{
		ll sum = 0;
		for (int i = mid+1; i < n; i++)
			if (mask&(1<<(i-mid)))
				sum += a[i];

		if (sum <= m)
		{
			ans++;

			ans += 1ll*get(t, m-sum);
		}
	}

	printf("%lld\n", ans);
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
bobek.cpp:81:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", &a[i]);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10