oj.uz

Submission #316323

# Submission time Handle Problem Language Result Execution time Memory
316323 2020-10-25T20:52:40 Z CaroLinda Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 403 ms 20948 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long

using namespace std ;

bool isOn(int i, int m) { return ((1<<i)&m) != 0 ; }

int main()
{
	int n ;
	ll budget ;

	scanf("%d %lld", &n, &budget ) ;

	vector<ll> vec[2] ;
	vec[0].resize( max(n/2,0) ) ;
	vec[1].resize( max(n - (n/2) , 0) ) ;

	for(int i = 0 ; i < n/2 ; i++ ) scanf("%lld", &vec[0][i]) ;
	for(int i = n/2 , j = 0 ; i < n ; i++, j++ ) scanf("%lld", &vec[1][j]) ;

	vector<ll> ways[2] ;
	long long ans = 0LL ;

	for(int i = 0, qtd ; i < 2 ; i++ )
	{
		qtd = (int)( vec[i].size() ) ;

		for(int j = 0 ; j < (1<<qtd) ; j++ )
		{
			long long mySum = 0 ;

			for(int g = 0 ; g < qtd ; g++ )
				if(isOn(g,j)) mySum += vec[i][g] ;

			ways[i].push_back(mySum) ;

		}

		sort(all(ways[i])) ;

	}

	for(long long mySum : ways[0] ) 
	{

		int l = 0 , r = sz(ways[1])-1 , mid , best = -1 ;

		while( l <= r )
		{
			mid = (l+r)>>1 ;

			if( mySum + ways[1][mid] <= budget )
			{
				best = mid ;
				l = mid+1 ;
			}
			else r = mid-1 ;

		}

		ans += 1LL + (ll)best ;

	}

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

}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:16:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   16 |  scanf("%d %lld", &n, &budget ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
bobek.cpp:22:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  for(int i = 0 ; i < n/2 ; i++ ) scanf("%lld", &vec[0][i]) ;
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~~
bobek.cpp:23:52: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  for(int i = n/2 , j = 0 ; i < n ; i++, j++ ) scanf("%lld", &vec[1][j]) ;
      |                                               ~~~~~^~~~~~~~~~~~~~~~~~~~

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 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 0 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2056 KB Output is correct
2 Correct 95 ms 5476 KB Output is correct
3 Correct 402 ms 20948 KB Output is correct
4 Correct 94 ms 5480 KB Output is correct
5 Correct 16 ms 1656 KB Output is correct
6 Correct 10 ms 1020 KB Output is correct
7 Correct 21 ms 1656 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2924 KB Output is correct
2 Correct 33 ms 2040 KB Output is correct
3 Correct 159 ms 10764 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 8 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 67 ms 3564 KB Output is correct
2 Correct 140 ms 6572 KB Output is correct
3 Correct 139 ms 6628 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 90 ms 6628 KB Output is correct
6 Correct 333 ms 20816 KB Output is correct
7 Correct 133 ms 6628 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 12764 KB Output is correct
2 Correct 32 ms 2040 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 8 ms 1020 KB Output is correct
6 Correct 270 ms 12892 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 32 ms 2040 KB Output is correct
2 Correct 92 ms 5488 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 11 ms 1148 KB Output is correct
5 Correct 94 ms 6632 KB Output is correct
6 Correct 30 ms 2040 KB Output is correct
7 Correct 369 ms 20820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 20816 KB Output is correct
2 Correct 33 ms 2040 KB Output is correct
3 Correct 11 ms 1020 KB Output is correct
4 Correct 403 ms 20816 KB Output is correct
5 Correct 128 ms 10588 KB Output is correct
6 Correct 20 ms 1656 KB Output is correct
7 Correct 41 ms 2932 KB Output is correct