Submission #1369348


Source Code Expand

#include<iostream>
#include<algorithm>
using namespace std;

#define int long long
int w[50];
int pw[1 << 17];
signed main() {
	int n, x;
	cin >> n >> x;
	for (int i = 0; i < n; i++)cin >> w[i];
	int n2 = n / 2;
	for (int i = 0; i<1 << n2; i++) {
		int sw = 0;
		for (int j = 0; j<n2; j++) {
			if (i >> j & 1) {
				sw += w[j];
			}
		}
		pw[i] = sw;
	}

	sort(pw, pw + (1 << n2));

	int res = 0;
	for (int i = 0; i<1 << (n - n2); i++) {
		int sw = 0;
		for (int j = 0; j<n - n2; j++) {
			if (i >> j & 1) {
				sw += w[n2 + j];
			}
		}
		if (sw <= x) {
			if (binary_search(pw, pw + (1<<n2), x - sw)) {
				auto a=equal_range(pw, pw + (1<<n2), x - sw);
				res += distance(a.first, a.second);
			}
		}
	}
	cout << res << endl;
}

Submission Info

Submission Time
Task C - 無駄なものが嫌いな人
User Rho17
Language C++14 (GCC 5.4.1)
Score 100
Code Size 771 Byte
Status AC
Exec Time 23 ms
Memory 768 KB

Judge Result

Set Name All
Score / Max Score 100 / 100
Status
AC × 28
Set Name Test Cases
All max_1.txt, max_2.txt, max_3.txt, max_4.txt, pair_1.txt, pair_2.txt, power2_1.txt, power2_2.txt, power2_3.txt, power2_4.txt, power2_5.txt, random_1.txt, random_2.txt, random_3.txt, random_4.txt, random_5.txt, random_6.txt, random_7.txt, random_8.txt, random_9.txt, sample_1.txt, sample_2.txt, sample_3.txt, sample_4.txt, small_1.txt, small_2.txt, small_3.txt, small_4.txt
Case Name Status Exec Time Memory
max_1.txt AC 14 ms 768 KB
max_2.txt AC 15 ms 768 KB
max_3.txt AC 13 ms 768 KB
max_4.txt AC 17 ms 768 KB
pair_1.txt AC 18 ms 768 KB
pair_2.txt AC 23 ms 768 KB
power2_1.txt AC 14 ms 768 KB
power2_2.txt AC 13 ms 768 KB
power2_3.txt AC 18 ms 768 KB
power2_4.txt AC 17 ms 768 KB
power2_5.txt AC 2 ms 256 KB
random_1.txt AC 11 ms 512 KB
random_2.txt AC 12 ms 512 KB
random_3.txt AC 12 ms 768 KB
random_4.txt AC 17 ms 768 KB
random_5.txt AC 13 ms 768 KB
random_6.txt AC 14 ms 512 KB
random_7.txt AC 23 ms 768 KB
random_8.txt AC 16 ms 768 KB
random_9.txt AC 9 ms 512 KB
sample_1.txt AC 1 ms 256 KB
sample_2.txt AC 1 ms 256 KB
sample_3.txt AC 1 ms 256 KB
sample_4.txt AC 1 ms 256 KB
small_1.txt AC 1 ms 256 KB
small_2.txt AC 1 ms 256 KB
small_3.txt AC 1 ms 256 KB
small_4.txt AC 1 ms 256 KB