oj.uz

Submission #40952

# Submission time Handle Problem Language Result Execution time Memory
40952 2018-02-10T03:21:31 Z wzy Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 604 ms 21464 KB 
#include <stdio.h>
#include <vector>
#include <stdint.h>
#include <algorithm>
using namespace std;
#define pb push_back
#define int long long
int ans = 1 , v1[50] , v2[50] , n , m;


int32_t main(){
	scanf("%lld%lld" , &n , &m);
	int sz1 = n / 2 , sz2 =  n - sz1;
	for(int i = 0 ; i < n;i++){
		if(sz1){
			scanf("%lld" , &v1[n/2 - sz1]);
			sz1--;
		}
		else{
			scanf("%lld" , &v2[(n - n/2) - sz2]);
			sz2--;
		}
	}
	vector<int> value1 , value2;
	sz1 = n/2 , sz2 = n - sz1;
	for(int i = 1 ; i < (1<<sz1) ; i++){
		int sum = 0;
		for(int j = 0 ; j < n ; j++){
			if(1<<j & i) sum += v1[j];
		}
		if(sum <= m)
		value1.pb(sum);
	}
	for(int i = 1 ; i < (1<<sz2) ; i++){
		int sum = 0;
		for(int j = 0 ; j < n ; j++){
			if(1<<j & i) sum += v2[j];
		}
		if(sum <= m)
		value2.pb(sum);
	}
	ans += value1.size() + value2.size();
	sort(value1.begin() , value1.end());
	sort(value2.begin() , value2.end());
	for(int i = 0 ; i < value1.size() ; i++){
		int l = 0 , r = (int)value2.size() - 1;
		int ansj = -1;
		while(l<= r){
			int mid = (l+r)/2;
			if(value2[mid] + value1[i] <= m){
				l = mid + 1;
				ansj = max(ansj , mid);
			}
			else r = mid - 1;
		}
		if(ansj != -1) ans += ansj + 1;
	}
	printf("%lld\n" , ans);
}

Compilation message

bobek.cpp: In function 'int32_t main()':
bobek.cpp:45:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < value1.size() ; i++){
                    ^
bobek.cpp:12:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld" , &n , &m);
                             ^
bobek.cpp:16:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld" , &v1[n/2 - sz1]);
                                  ^
bobek.cpp:20:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld" , &v2[(n - n/2) - sz2]);
                                        ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 2340 KB Output is correct
2 Correct 135 ms 5788 KB Output is correct
3 Correct 588 ms 21176 KB Output is correct
4 Correct 125 ms 21176 KB Output is correct
5 Correct 26 ms 21176 KB Output is correct
6 Correct 15 ms 21176 KB Output is correct
7 Correct 17 ms 21176 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 21176 KB Output is correct
2 Correct 46 ms 21176 KB Output is correct
3 Correct 222 ms 21176 KB Output is correct
4 Correct 2 ms 21176 KB Output is correct
5 Correct 13 ms 21176 KB Output is correct
6 Correct 32 ms 21176 KB Output is correct
7 Correct 16 ms 21176 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 21176 KB Output is correct
2 Correct 192 ms 21176 KB Output is correct
3 Correct 185 ms 21176 KB Output is correct
4 Correct 2 ms 21176 KB Output is correct
5 Correct 132 ms 21176 KB Output is correct
6 Correct 524 ms 21360 KB Output is correct
7 Correct 93 ms 21360 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 407 ms 21360 KB Output is correct
2 Correct 43 ms 21360 KB Output is correct
3 Correct 16 ms 21360 KB Output is correct
4 Correct 1 ms 21360 KB Output is correct
5 Correct 12 ms 21360 KB Output is correct
6 Correct 374 ms 21360 KB Output is correct
7 Correct 17 ms 21360 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 21360 KB Output is correct
2 Correct 129 ms 21360 KB Output is correct
3 Correct 16 ms 21360 KB Output is correct
4 Correct 15 ms 21360 KB Output is correct
5 Correct 139 ms 21360 KB Output is correct
6 Correct 46 ms 21360 KB Output is correct
7 Correct 304 ms 21360 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 21464 KB Output is correct
2 Correct 46 ms 21464 KB Output is correct
3 Correct 20 ms 21464 KB Output is correct
4 Correct 604 ms 21464 KB Output is correct
5 Correct 189 ms 21464 KB Output is correct
6 Correct 29 ms 21464 KB Output is correct
7 Correct 29 ms 21464 KB Output is correct