oj.uz

Submission #24548

# Submission time Handle Problem Language Result Execution time Memory
24548 2017-06-10T10:42:58 Z Bruteforceman Ice Hockey World Championship (CEOI15_bobek) C++11
100 / 100
 446 ms 26680 KB 
#include "bits/stdc++.h"
using namespace std;

void putStaff(vector <long long> v, vector <long long> &x) {
	int n = v.size();
	for(int i = 0; i < (1 << n); i++) {
		long long sum = 0;
		for(int j = 0; j < n; j++) {
			if((i >> j) & 1) {
				sum += v[j];
			}
		}
		x.push_back(sum);
	}
	sort(x.begin(), x.end());
}

int main(int argc, char const *argv[])
{
	int n;
	long long budget;
	cin >> n >> budget;
	long long *a = new long long [n];

	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int half = n >> 1;
	
	vector <long long> p1, p2;
	vector <long long> sum1, sum2;

	for(int i = 0; i < n; i++) {
		if(i < half) p1.push_back(a[i]);
		else p2.push_back(a[i]);
	}
	delete a;

	putStaff(p1, sum1);
	putStaff(p2, sum2);

	long long ans = 0;
	for(auto i : sum1) {
		ans += upper_bound(sum2.begin(), sum2.end(), budget - i) - sum2.begin();
	}
	cout << ans << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 4156 KB Output is correct
2 Correct 109 ms 8248 KB Output is correct
3 Correct 446 ms 26680 KB Output is correct
4 Correct 106 ms 8248 KB Output is correct
5 Correct 13 ms 3640 KB Output is correct
6 Correct 13 ms 2872 KB Output is correct
7 Correct 23 ms 3640 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 5176 KB Output is correct
2 Correct 29 ms 4156 KB Output is correct
3 Correct 196 ms 14392 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 6 ms 2872 KB Output is correct
6 Correct 26 ms 3640 KB Output is correct
7 Correct 23 ms 3640 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 6204 KB Output is correct
2 Correct 156 ms 10300 KB Output is correct
3 Correct 153 ms 10300 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 96 ms 10300 KB Output is correct
6 Correct 379 ms 26680 KB Output is correct
7 Correct 139 ms 10300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 18492 KB Output is correct
2 Correct 36 ms 4156 KB Output is correct
3 Correct 9 ms 2872 KB Output is correct
4 Correct 0 ms 2020 KB Output is correct
5 Correct 6 ms 2872 KB Output is correct
6 Correct 299 ms 18492 KB Output is correct
7 Correct 19 ms 3640 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 4156 KB Output is correct
2 Correct 99 ms 8248 KB Output is correct
3 Correct 13 ms 2872 KB Output is correct
4 Correct 9 ms 2872 KB Output is correct
5 Correct 103 ms 10300 KB Output is correct
6 Correct 29 ms 4156 KB Output is correct
7 Correct 399 ms 26680 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 26680 KB Output is correct
2 Correct 36 ms 4156 KB Output is correct
3 Correct 9 ms 2872 KB Output is correct
4 Correct 443 ms 26680 KB Output is correct
5 Correct 149 ms 14392 KB Output is correct
6 Correct 23 ms 3640 KB Output is correct
7 Correct 46 ms 5176 KB Output is correct