oj.uz

답안 #1054130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1054130 2024-08-12T06:43:58 Z vako_p Ice Hockey World Championship (CEOI15_bobek) C++14
100 / 100
 902 ms 78544 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back

const int mxN = 50;
ll n,m,a[mxN];
int _p[2000000];
int* p = _p + 5;
map<ll,int> ans;
vector<ll> v;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> a[i]; 
	v.pb(0);
	ans[0]++;
	for(int bit = 1; bit < (1 << (n / 2)); bit++){
		ll x = 0;
		for(int i = 0; i < (n / 2); i++) x += a[i] * (((1 << i) & bit) > 0);
		if(x <= m){
			if(!ans[x]) v.pb(x);
			ans[x]++;
		} 
//		cout << x << ' ' << ans[x] << '\n';
	} 
	sort(v.begin(), v.end());
	for(int i = 0; i < v.size(); i++) p[i] = p[i - 1] + ans[v[i]];
	ll res = p[v.size() - 1];
	for(int bit = 1; bit < (1 << ((n + 1) / 2)); bit++){
		ll x = 0;
		for(int i = 0; i < (n + 1) / 2; i++) x += a[i + n / 2] * (((1 << i) & bit) > 0);
		auto it = upper_bound(v.begin(), v.end(), m - x); 
		if(it != v.begin())	res += p[it - v.begin() - 1];
	}
	cout << res;
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:31:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for(int i = 0; i < v.size(); i++) p[i] = p[i - 1] + ans[v[i]];
      |                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 1272 KB Output is correct
2 Correct 125 ms 14608 KB Output is correct
3 Correct 589 ms 34680 KB Output is correct
4 Correct 121 ms 15196 KB Output is correct
5 Correct 3 ms 344 KB Output is correct
6 Correct 6 ms 860 KB Output is correct
7 Correct 2 ms 348 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 1752 KB Output is correct
2 Correct 31 ms 6040 KB Output is correct
3 Correct 96 ms 1116 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 17 ms 2264 KB Output is correct
7 Correct 2 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 10184 KB Output is correct
2 Correct 134 ms 11372 KB Output is correct
3 Correct 126 ms 11388 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 15 ms 464 KB Output is correct
6 Correct 176 ms 1740 KB Output is correct
7 Correct 12 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 439 ms 39348 KB Output is correct
2 Correct 33 ms 7120 KB Output is correct
3 Correct 14 ms 2776 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 309 ms 39436 KB Output is correct
7 Correct 2 ms 348 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 7124 KB Output is correct
2 Correct 161 ms 20928 KB Output is correct
3 Correct 13 ms 2776 KB Output is correct
4 Correct 13 ms 2776 KB Output is correct
5 Correct 17 ms 472 KB Output is correct
6 Correct 30 ms 7044 KB Output is correct
7 Correct 35 ms 348 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 882 ms 78512 KB Output is correct
2 Correct 36 ms 7116 KB Output is correct
3 Correct 15 ms 2776 KB Output is correct
4 Correct 902 ms 78544 KB Output is correct
5 Correct 23 ms 344 KB Output is correct
6 Correct 25 ms 7124 KB Output is correct
7 Correct 4 ms 348 KB Output is correct