Submission #681722

#	Time	Username	Problem	Language	Result	Execution time	Memory
681722		Doncho_Bonboncho	Ice Hockey World Championship (CEOI15_bobek)	C++14	100 / 100	325 ms	20956 KiB

bobek

#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const int MAX_N = 1e6;
const int INF = 1e9;
const int mod = 1e9 + 7;

ll a[MAX_N];
std::vector<ll> l, r;

int main () {

	std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);

	ll n, m;
	std::cin>>n>>m;

	for( int i=0 ; i<n ; i++ ) std::cin>>a[i];

	int mid = n/2;
	for( int mask = 0; mask < ( 1 << mid ) ; mask++ ){
		ll currSum = 0;
		for( int j=0 ; j<mid ; j++ )
			if( (1<<j)&mask ) currSum += a[j];
		l.push_back( currSum );
	//	std::cerr<<"l "<<currSum<<"\n";
	}
	for( int mask = 0; mask < ( 1 << ( n-mid) ) ; mask++ ){
		ll currSum = 0;
		for( int j=mid ; j<n ;  j++ )
			if( (1<<(j - mid))&mask ) currSum += a[j];
		r.push_back( currSum );
	//	std::cerr<<"r "<<currSum<<"\n";
	}

	std::sort( l.begin(), l.end() );
	std::sort( r.begin(), r.end() );

	ll nas = 0;
	for( ll i=0 ; i<l.size() ; i++ ){
		ll cur = m-l[i];
		ll ind = std::upper_bound( r.begin(), r.end(), cur ) - r.begin();
		nas += ind;
	}
	std::cout<<nas<<"\n";

	/*
	for( int i=0 ; i<n ; i++ ){
		ll curr = a[i];
		int sz = v.size();
		for( int j=0 ; j<sz ; j++ ){
			ll currS = v[j] + curr;
		//	std::cerr<<v[j]<<" + "<<curr<<" = "<<currS<<" ? "<<m<<"\n";
			if( currS <= m ){
		//		std::cerr<<" mina\n ";
				v.push_back( currS );
			}
		}
		//if( curr < m ) v.push_back( curr );
	}

	std::cout<<v.size()<<"\n";
	*/

	return 0;
}

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:42:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for( ll i=0 ; i<l.size() ; 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