oj.uz

Submission #552836

# Submission time Handle Problem Language Result Execution time Memory
552836 2022-04-24T06:54:11 Z dsyz Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 307 ms 20808 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	vector<ll> front;
	vector<ll> back;
	for(ll i = 0;i < (N + 1) / 2;i++){
		front.push_back(arr[i]);
	}
	for(ll i = (N + 1) / 2;i < N;i++){
		back.push_back(arr[i]);
	}
	vector<ll> v1;
	vector<ll> v2;
	for(ll bitmask = 0;bitmask < ll(1ll << front.size());bitmask++){
		ll sum = 0;
		for(ll i = 0;i < front.size();i++){
			if(ll(1ll<<i) & bitmask){
				sum += front[i];
			}
		}
		v1.push_back(sum);
	}
	for(ll bitmask = 0;bitmask < ll(1ll << back.size());bitmask++){
		ll sum = 0;
		for(ll i = 0;i < back.size();i++){
			if(ll(1ll<<i) & bitmask){
				sum += back[i];
			}
		}
		v2.push_back(sum);
	}
	sort(v1.begin(),v1.end());
	sort(v2.begin(),v2.end());
	ll sum = 0;
	ll ptr = v2.size() - 1;
	for(ll i = 0;i < v1.size();i++){
		while(ptr >= 0 && v1[i] + v2[ptr] > M){  //when ptr == -1 then there is no possible way for v1
			ptr--;
		}
		sum += (ptr + 1);
	}
	cout<<sum<<'\n';
}

Compilation message

bobek.cpp: In function 'int main()':
bobek.cpp:25:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for(ll i = 0;i < front.size();i++){
      |                ~~^~~~~~~~~~~~~~
bobek.cpp:34:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(ll i = 0;i < back.size();i++){
      |                ~~^~~~~~~~~~~~~
bobek.cpp:45:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |  for(ll i = 0;i < v1.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 1 ms 212 KB Output is correct
2 Correct 1 ms 316 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 1 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 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 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2384 KB Output is correct
2 Correct 70 ms 5428 KB Output is correct
3 Correct 307 ms 20784 KB Output is correct
4 Correct 71 ms 5400 KB Output is correct
5 Correct 13 ms 1620 KB Output is correct
6 Correct 10 ms 964 KB Output is correct
7 Correct 17 ms 1548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2888 KB Output is correct
2 Correct 25 ms 2388 KB Output is correct
3 Correct 127 ms 10552 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 984 KB Output is correct
6 Correct 17 ms 1704 KB Output is correct
7 Correct 16 ms 1612 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 4424 KB Output is correct
2 Correct 112 ms 8520 KB Output is correct
3 Correct 114 ms 8504 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 74 ms 8580 KB Output is correct
6 Correct 251 ms 20780 KB Output is correct
7 Correct 103 ms 8468 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 16736 KB Output is correct
2 Correct 25 ms 2316 KB Output is correct
3 Correct 9 ms 856 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 6 ms 964 KB Output is correct
6 Correct 221 ms 16736 KB Output is correct
7 Correct 16 ms 1620 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2336 KB Output is correct
2 Correct 72 ms 5336 KB Output is correct
3 Correct 8 ms 856 KB Output is correct
4 Correct 8 ms 984 KB Output is correct
5 Correct 75 ms 8508 KB Output is correct
6 Correct 26 ms 2304 KB Output is correct
7 Correct 290 ms 20808 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 20788 KB Output is correct
2 Correct 25 ms 2256 KB Output is correct
3 Correct 9 ms 920 KB Output is correct
4 Correct 294 ms 20796 KB Output is correct
5 Correct 102 ms 10516 KB Output is correct
6 Correct 16 ms 1492 KB Output is correct
7 Correct 34 ms 2828 KB Output is correct