ACdream 1726 A Math game

A Math game

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 256000/128000KB (Java/Others)

Problem Description

Recently, Losanto find an interesting Math game. The rule is simple: Tell you a number H, and you can choose some numbers from a set {a[1],a[2],......,a[n]}.If the sum of the number you choose is H, then you win. Losanto just want to know whether he can win the game.

Input

There are several cases.
In each case, there are two numbers in the first line n (the size of the set) and H. The second line has n numbers {a[1],a[2],......,a[n]}.0<n<=40, 0<=H<10^9, 0<=a[i]<10^9,All the numbers are integers.

Output

If Losanto could win the game, output "Yes" in a line. Else output "No" in a line.

Sample Input

10 87
2 3 4 5 7 9 10 11 12 13
10 38
2 3 4 5 7 9 10 11 12 13

Sample Output

No
Yes

Source

第九届北京化工大学程序设计竞赛

Manager

rihkddd

解题：用vector 差点T成傻逼

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 50;
 4 typedef long long LL;
 5 LL sum,A[2000100],B[2000010];
 6 int x,y;
 7 int main() {
 8     int n;
 9     while(~scanf("%d%lld",&n,&sum)) {
10         int a = (n>>1),b = n-a;
11         x = y = 0;
12         LL tmp;
13         bool flag = sum?false:true;
14         for(int i = 0; i < a; ++i) {
15             scanf("%lld",&tmp);
16             for(int j = x - 1; j >= 0 && !flag; --j) {
17                 A[x++] = A[j] + tmp;
18                 if(A[j] + tmp == sum) flag = true;
19             }
20             A[x++] = tmp;
21             if(tmp == sum) flag = true;
22         }
23         for(int i = 0; i < b; ++i) {
24             scanf("%lld",&tmp);
25             for(int j = y-1; j >= 0 && !flag; --j) {
26                 B[y++] = (B[j] + tmp);
27                 if(B[j] + tmp == sum) flag = true;
28             }
29             B[y++] = tmp;
30             if(tmp == sum) flag = true;
31         }
32         sort(B,B + y);
33         sort(A,A + x);
34         if(!flag && x && y && A[x-1] + B[y-1] >= sum && A[0] + B[0] <= sum){
35             for(int i = 0; i < x && !flag; ++i){
36                 if(A[i] + B[y-1] < sum) continue;
37                 flag = binary_search(B,B + y,sum - A[i]);
38                 if(A[i] + B[0] > sum) break;
39             }
40         }
41         puts(flag?"Yes":"No");
42     }
43     return 0;
44 }

View Code