Submission #1015518
Source Code Expand
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;
int main() {
ll n, x;
scanf("%lld %lld", &n, &x);
vll w(n);
rep(i, n) {
scanf("%lld", &w[i]);
}
sort(all(w));
w.erase(upper_bound(all(w), x), end(w));
int len = w.size();
int len1 = len / 2;
int len2 = len - len1;
vll w1(len1);
vll w2(len2);
rep (i, len1) {
w1[i] = w[i];
}
rep (i, len2) {
w2[i] = w[i + len1];
}
ll loop;
loop = 1;
rep (i, len1) {
loop *= 2;
}
map<ll, ll> psum1;
rep (i, loop) {
ll psum = 0;
rep (j, len1) {
if ((i >> j) % 2 == 1) {
psum += w1[j];
}
}
psum1[psum] += 1;
}
loop = 1;
rep (i, len2) {
loop *= 2;
}
map<ll, ll> psum2;
rep (i, loop) {
ll psum = 0;
rep (j, len2) {
if ((i >> j) % 2 == 1) {
psum += w2[j];
}
}
psum2[psum] += 1;
}
ll ans = 0;
for (auto p : psum1) {
ll s1 = p.first;
ans += p.second * psum2[x - s1];
}
printf("%lld\n", ans);
return 0;
}
Submission Info
Submission Time |
|
Task |
C - 無駄なものが嫌いな人 |
User |
tspcx |
Language |
C++11 (GCC 4.8.1) |
Score |
100 |
Code Size |
1974 Byte |
Status |
AC |
Exec Time |
86 ms |
Memory |
13036 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:43:29: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld %lld", &n, &x);
^
./Main.cpp:46:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &w[i]);
^
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, small_1.txt, small_2.txt, small_3.txt, small_4.txt |
Case Name |
Status |
Exec Time |
Memory |
max_1.txt |
AC |
27 ms |
808 KB |
max_2.txt |
AC |
32 ms |
884 KB |
max_3.txt |
AC |
28 ms |
796 KB |
max_4.txt |
AC |
29 ms |
796 KB |
pair_1.txt |
AC |
86 ms |
12196 KB |
pair_2.txt |
AC |
30 ms |
800 KB |
power2_1.txt |
AC |
33 ms |
1192 KB |
power2_2.txt |
AC |
28 ms |
884 KB |
power2_3.txt |
AC |
29 ms |
796 KB |
power2_4.txt |
AC |
30 ms |
752 KB |
power2_5.txt |
AC |
23 ms |
1824 KB |
random_1.txt |
AC |
59 ms |
8864 KB |
random_2.txt |
AC |
66 ms |
8992 KB |
random_3.txt |
AC |
86 ms |
13036 KB |
random_4.txt |
AC |
86 ms |
12964 KB |
random_5.txt |
AC |
32 ms |
800 KB |
random_6.txt |
AC |
29 ms |
796 KB |
random_7.txt |
AC |
31 ms |
928 KB |
random_8.txt |
AC |
46 ms |
3060 KB |
random_9.txt |
AC |
61 ms |
8864 KB |
sample_1.txt |
AC |
18 ms |
796 KB |
sample_2.txt |
AC |
19 ms |
796 KB |
sample_3.txt |
AC |
21 ms |
864 KB |
sample_4.txt |
AC |
18 ms |
928 KB |
small_1.txt |
AC |
18 ms |
800 KB |
small_2.txt |
AC |
17 ms |
912 KB |
small_3.txt |
AC |
18 ms |
796 KB |
small_4.txt |
AC |
18 ms |
920 KB |