Submission #294006

#	Time	Username	Problem	Language	Result	Execution time	Memory
294006		Lawliet	Ice Hockey World Championship (CEOI15_bobek)	C++17	100 / 100	417 ms	20896 KiB

bobek

#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 (stderr)

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