Submission #1381026
Source Code Expand
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools sys.setrecursionlimit(10**7) inf = 10**20 mod = 10**9 + 7 def LI(): return [int(x) for x in sys.stdin.readline().split()] def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()] def LF(): return [float(x) for x in sys.stdin.readline().split()] def LS(): return sys.stdin.readline().split() def I(): return int(sys.stdin.readline()) def F(): return float(sys.stdin.readline()) def S(): return input() def main(): N,X = LI() W = sorted([I() for _ in range(N)], reverse=True) d = collections.defaultdict(int) d[0] = 1 for c in W[N//2:]: t = collections.defaultdict(int) for k,v in d.items(): if k+c > X: continue t[k+c] += v for k,v in t.items(): d[k] += v d2 = collections.defaultdict(int) d2[0] = 1 for c in W[:N//2]: t = collections.defaultdict(int) for k,v in d2.items(): if k+c > X: continue t[k+c] += v for k,v in t.items(): d2[k] += v r = 0 for k,v in d.items(): r += v * d2[X-k] return r print(main())
Submission Info
Submission Time | |
---|---|
Task | C - 無駄なものが嫌いな人 |
User | iehn |
Language | Python (3.4.3) |
Score | 100 |
Code Size | 1293 Byte |
Status | AC |
Exec Time | 166 ms |
Memory | 28716 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 | 41 ms | 5328 KB |
max_2.txt | AC | 44 ms | 5588 KB |
max_3.txt | AC | 41 ms | 5460 KB |
max_4.txt | AC | 42 ms | 5456 KB |
pair_1.txt | AC | 166 ms | 28696 KB |
pair_2.txt | AC | 42 ms | 5584 KB |
power2_1.txt | AC | 45 ms | 6100 KB |
power2_2.txt | AC | 43 ms | 5588 KB |
power2_3.txt | AC | 41 ms | 5460 KB |
power2_4.txt | AC | 41 ms | 5460 KB |
power2_5.txt | AC | 52 ms | 8156 KB |
random_1.txt | AC | 139 ms | 27168 KB |
random_2.txt | AC | 139 ms | 27172 KB |
random_3.txt | AC | 86 ms | 11992 KB |
random_4.txt | AC | 162 ms | 28716 KB |
random_5.txt | AC | 43 ms | 5460 KB |
random_6.txt | AC | 44 ms | 5712 KB |
random_7.txt | AC | 44 ms | 5712 KB |
random_8.txt | AC | 76 ms | 11340 KB |
random_9.txt | AC | 115 ms | 18344 KB |
sample_1.txt | AC | 41 ms | 5456 KB |
sample_2.txt | AC | 41 ms | 5460 KB |
sample_3.txt | AC | 42 ms | 5588 KB |
sample_4.txt | AC | 41 ms | 5456 KB |
small_1.txt | AC | 41 ms | 5464 KB |
small_2.txt | AC | 41 ms | 5464 KB |
small_3.txt | AC | 41 ms | 5456 KB |
small_4.txt | AC | 41 ms | 5456 KB |