oj.uz

Submission #681722

# Submission time Handle Problem Language Result Execution time Memory
681722 2023-01-13T22:41:04 Z Doncho_Bonboncho Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 325 ms 20956 KB 
#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

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

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1940 KB Output is correct
2 Correct 80 ms 5452 KB Output is correct
3 Correct 325 ms 20720 KB Output is correct
4 Correct 78 ms 5340 KB Output is correct
5 Correct 13 ms 1620 KB Output is correct
6 Correct 9 ms 972 KB Output is correct
7 Correct 18 ms 1620 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2820 KB Output is correct
2 Correct 28 ms 2008 KB Output is correct
3 Correct 128 ms 10672 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 7 ms 984 KB Output is correct
6 Correct 17 ms 1620 KB Output is correct
7 Correct 16 ms 1620 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 3444 KB Output is correct
2 Correct 114 ms 6576 KB Output is correct
3 Correct 117 ms 6596 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 76 ms 6624 KB Output is correct
6 Correct 271 ms 20788 KB Output is correct
7 Correct 105 ms 6552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 12696 KB Output is correct
2 Correct 26 ms 1960 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 1 ms 328 KB Output is correct
5 Correct 7 ms 972 KB Output is correct
6 Correct 226 ms 12756 KB Output is correct
7 Correct 16 ms 1620 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 1956 KB Output is correct
2 Correct 75 ms 5356 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 9 ms 984 KB Output is correct
5 Correct 77 ms 6612 KB Output is correct
6 Correct 25 ms 1996 KB Output is correct
7 Correct 301 ms 20824 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 312 ms 20956 KB Output is correct
2 Correct 27 ms 2008 KB Output is correct
3 Correct 9 ms 984 KB Output is correct
4 Correct 324 ms 20784 KB Output is correct
5 Correct 104 ms 10580 KB Output is correct
6 Correct 18 ms 1612 KB Output is correct
7 Correct 32 ms 2884 KB Output is correct