oj.uz

Submission #1054120

# Submission time Handle Problem Language Result Execution time Memory
1054120 2024-08-12T06:36:34 Z vako_p Ice Hockey World Championship (CEOI15_bobek) C++14
90 / 100
 1000 ms 132024 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],_p[2000000];
ll* p = _p + 2;
map<ll,ll> ans;
set<ll> s;
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]; 
	s.insert(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){
			ans[x]++;
			s.insert(x); 
		} 
//		cout << x << ' ' << ans[x] << '\n';
	} 
	for(auto it : s) v.pb(it);
	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++){
      |                 ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 420 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 #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 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

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1968 KB Output is correct
2 Correct 144 ms 22632 KB Output is correct
3 Correct 750 ms 58536 KB Output is correct
4 Correct 151 ms 23748 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 9 ms 1236 KB Output is correct
7 Correct 2 ms 344 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2872 KB Output is correct
2 Correct 33 ms 8592 KB Output is correct
3 Correct 91 ms 1616 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 18 ms 5856 KB Output is correct
7 Correct 2 ms 348 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 15308 KB Output is correct
2 Correct 162 ms 17344 KB Output is correct
3 Correct 155 ms 17356 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 17 ms 476 KB Output is correct
6 Correct 180 ms 2820 KB Output is correct
7 Correct 11 ms 348 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 66524 KB Output is correct
2 Correct 34 ms 10696 KB Output is correct
3 Correct 15 ms 6624 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 443 ms 66204 KB Output is correct
7 Correct 2 ms 344 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10292 KB Output is correct
2 Correct 209 ms 33400 KB Output is correct
3 Correct 16 ms 6624 KB Output is correct
4 Correct 17 ms 6620 KB Output is correct
5 Correct 24 ms 476 KB Output is correct
6 Correct 32 ms 10452 KB Output is correct
7 Correct 30 ms 348 KB Output is correct

Subtask #10
0 / 10.0

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