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 |
|
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 |