oj.uz

Submission #681721

# Submission time Handle Problem Language Result Execution time Memory
681721 2023-01-13T22:40:09 Z Doncho_Bonboncho Ice Hockey World Championship (CEOI15_bobek) C++14
40 / 100
 1000 ms 9336 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( int 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:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |  for( int i=0 ; i<l.size() ; i++ ){
      |                 ~^~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 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 3 ms 340 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Correct 9 ms 340 KB Output is correct
7 Correct 3 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 705 ms 3416 KB Output is correct
2 Execution timed out 1090 ms 5460 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 943 ms 4676 KB Output is correct
2 Correct 715 ms 3676 KB Output is correct
3 Execution timed out 1072 ms 6320 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 730 ms 5632 KB Output is correct
2 Execution timed out 1082 ms 8872 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

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