oj.uz

Submission #108374

# Submission time Handle Problem Language Result Execution time Memory
108374 2019-04-28T19:10:18 Z luciocf Ice Hockey World Championship (CEOI15_bobek) C++14
0 / 100
 732 ms 49496 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 3472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 6548 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 6572 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 563 ms 25032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 3436 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 732 ms 49496 KB Output isn't correct
2 Halted 0 ms 0 KB -