oj.uz

Submission #981885

# Submission time Handle Problem Language Result Execution time Memory
981885 2024-05-13T16:01:31 Z LOLOLO Ice Hockey World Championship (CEOI15_bobek) C++17
100 / 100
 176 ms 22832 KB 
#include <bits/stdc++.h>
using namespace std;
 
int n;
long long M;
long long a[44];
long long ans;
vector< long long > v1, v2;
 
void bt(int pos, int lim, long long sum, vector<long long> &v) {
	if (pos == lim) {
		v.push_back(sum); return;
	}
	bt(pos + 1, lim, sum, v);
	bt(pos + 1, lim, sum + a[pos], v);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> M;
	for (int i = 0; i < n; ++i) cin >> a[i];
	bt(0, n / 2, 0, v1);
	bt(n / 2, n, 0, v2);
 
	sort(v1.begin(), v1.end());
	sort(v2.begin(), v2.end());
 
	int ptr = v2.size() - 1;
	for (int i = 0; i < v1.size(); ++i) {
		if (v1[i] > M) break;
		while(ptr >= 0 && v2[ptr] > M - v1[i]) --ptr;
		// [0...ptr]
		ans += ptr + 1;
	}
 
	printf("%lld\n", ans);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 460 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 452 KB Output is correct
7 Correct 1 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 1 ms 348 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2144 KB Output is correct
2 Correct 41 ms 5588 KB Output is correct
3 Correct 175 ms 22732 KB Output is correct
4 Correct 42 ms 5588 KB Output is correct
5 Correct 8 ms 1756 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct
7 Correct 10 ms 1496 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3032 KB Output is correct
2 Correct 14 ms 2144 KB Output is correct
3 Correct 66 ms 11216 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 9 ms 1592 KB Output is correct
7 Correct 9 ms 1752 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3676 KB Output is correct
2 Correct 75 ms 8280 KB Output is correct
3 Correct 63 ms 7768 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 38 ms 8024 KB Output is correct
6 Correct 136 ms 22832 KB Output is correct
7 Correct 62 ms 6744 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 14940 KB Output is correct
2 Correct 14 ms 2144 KB Output is correct
3 Correct 5 ms 992 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 992 KB Output is correct
6 Correct 123 ms 12960 KB Output is correct
7 Correct 9 ms 1756 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2144 KB Output is correct
2 Correct 40 ms 5588 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 33 ms 7000 KB Output is correct
6 Correct 13 ms 2144 KB Output is correct
7 Correct 168 ms 21792 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 21960 KB Output is correct
2 Correct 14 ms 2396 KB Output is correct
3 Correct 5 ms 1116 KB Output is correct
4 Correct 176 ms 21984 KB Output is correct
5 Correct 46 ms 10960 KB Output is correct
6 Correct 11 ms 1632 KB Output is correct
7 Correct 21 ms 2880 KB Output is correct