oj.uz

Submission #294006

# Submission time Handle Problem Language Result Execution time Memory
294006 2020-09-08T14:22:30 Z Lawliet Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 417 ms 20896 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 50;

int n;
lli S;

lli v[MAXN];

vector<lli> groups[2];

void findGroups(int L, int R, int ind)
{
	int sz = R - L + 1;

	for(int mask = 0 ; mask < (1 << sz) ; mask++)
	{
		lli sum = 0;

		for(int i = 0 ; i < sz ; i++)
			if( mask & (1 << i) ) sum += v[L + i];

		groups[ind].push_back( sum );
	}

	sort( groups[ind].begin() , groups[ind].end() );
}

int main()
{
	scanf("%d %lld",&n,&S);

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

	if( n <= 20 )
	{
		findGroups( 1 , n , 0 );

		int ans = 0;

		for(int i = 0 ; i < (int)groups[0].size() ; i++)
			if( groups[0][i] <= S ) ans++;

		printf("%d\n",ans);
		return 0;
	}

	int m = n/2;
	findGroups( 1 , m , 0 );
	findGroups( m + 1 , n , 1 );

	lli ans = 0;

	int p = (int)groups[1].size() - 1;

	for(int i = 0 ; i < (int)groups[0].size() ; i++)
	{
		while( p >= 0 && groups[0][i] + groups[1][p] > S )
			p--;

		ans += p + 1;
	}

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

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 1528 KB Output is correct
2 Correct 10 ms 1020 KB Output is correct
3 Correct 35 ms 1528 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 13 ms 1020 KB Output is correct
6 Correct 220 ms 8700 KB Output is correct
7 Correct 21 ms 1528 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 8676 KB Output is correct
2 Correct 43 ms 2548 KB Output is correct
3 Correct 10 ms 1020 KB Output is correct
4 Correct 10 ms 1020 KB Output is correct
5 Correct 133 ms 8676 KB Output is correct
6 Correct 20 ms 1528 KB Output is correct
7 Correct 20 ms 1528 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2040 KB Output is correct
2 Correct 86 ms 5476 KB Output is correct
3 Correct 366 ms 20816 KB Output is correct
4 Correct 87 ms 5476 KB Output is correct
5 Correct 15 ms 1656 KB Output is correct
6 Correct 13 ms 1020 KB Output is correct
7 Correct 30 ms 1656 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 2924 KB Output is correct
2 Correct 30 ms 2040 KB Output is correct
3 Correct 164 ms 10716 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 7 ms 1020 KB Output is correct
6 Correct 20 ms 1656 KB Output is correct
7 Correct 20 ms 1656 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 3572 KB Output is correct
2 Correct 145 ms 6748 KB Output is correct
3 Correct 129 ms 6628 KB Output is correct
4 Correct 41 ms 2548 KB Output is correct
5 Correct 88 ms 6672 KB Output is correct
6 Correct 330 ms 20896 KB Output is correct
7 Correct 151 ms 6632 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 266 ms 12768 KB Output is correct
2 Correct 35 ms 2040 KB Output is correct
3 Correct 13 ms 1020 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Correct 9 ms 1020 KB Output is correct
6 Correct 275 ms 12764 KB Output is correct
7 Correct 20 ms 1656 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 2040 KB Output is correct
2 Correct 87 ms 5476 KB Output is correct
3 Correct 10 ms 1020 KB Output is correct
4 Correct 10 ms 1020 KB Output is correct
5 Correct 95 ms 6628 KB Output is correct
6 Correct 30 ms 2040 KB Output is correct
7 Correct 417 ms 20816 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 357 ms 20816 KB Output is correct
2 Correct 32 ms 2040 KB Output is correct
3 Correct 10 ms 1020 KB Output is correct
4 Correct 371 ms 20816 KB Output is correct
5 Correct 125 ms 10644 KB Output is correct
6 Correct 20 ms 1560 KB Output is correct
7 Correct 40 ms 2924 KB Output is correct