oj.uz

Submission #108375

# Submission time Handle Problem Language Result Execution time Memory
108375 2019-04-28T19:18:20 Z luciocf Ice Hockey World Championship (CEOI15_bobek) C++14
40 / 100
 1000 ms 35140 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(), sz = 1;
		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, aux->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 1+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 = 1; 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 = 1; mask < (1<<k); mask++)
	{
		ll sum = 0;
		for (int i = mid; 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+1);
}

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
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 3524 KB Output is correct
2 Correct 535 ms 12680 KB Output is correct
3 Execution timed out 1073 ms 34852 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 209 ms 6392 KB Output is correct
2 Correct 88 ms 3448 KB Output is correct
3 Execution timed out 1072 ms 21768 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 206 ms 6392 KB Output is correct
2 Correct 780 ms 12688 KB Output is correct
3 Correct 785 ms 12792 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Execution timed out 1075 ms 3576 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 24992 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 3436 KB Output is correct
2 Correct 491 ms 12648 KB Output is correct
3 Correct 25 ms 1792 KB Output is correct
4 Correct 25 ms 1792 KB Output is correct
5 Execution timed out 1075 ms 5568 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 35140 KB Time limit exceeded
2 Halted 0 ms 0 KB -