Submission #57876
ソースコード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 | //header{{{ #include<bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<(n);++i) #define reps(i,n) for(int i=1;i<=(n);++i) #define all(x) (x).begin(),(x).end() #define setout(n,x) setw(n+1) << setfill(x) #define Fixed fixed << setprecision(10) #define int int64_t using pii = pair< int , int >; constexpr int INF = 0x3f3f3f3f; constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr int mod = 1e9+7; template < class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true ); } template < class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true ); } template < class T> using min_heap = priority_queue<T,vector<T>,greater<T> >; template < class T> using max_heap = priority_queue<T>; template < class A, class B> using umap = unordered_map<A,B>; int gcd( int a, int b){ return b ? gcd(b,a % b) : a;} int lcm( int a, int b){ return a / gcd(a,b) * b;} //}}} signed main(){ cin.tie(0); ios::sync_with_stdio( false ); int n,q; cin >> n >> q; bool flg[21] = {}; vector< int > a; rep(i,n){ int x; cin >> x; if (!flg[x+10]){ a.emplace_back(x); flg[x+10] = true ; } } bool dp[a.size()+1][120] = {}; dp[0][55] = true ; rep(i,a.size()){ rep(j,111){ if (dp[i][j]){ dp[i+1][j] |= dp[i][j]; dp[i+1][j+a[i]] |= dp[i][j]; } } } rep(i,q){ int x; cin >> x; if (x < -55 || 55 < x){ cout << "Impossible\n" ; continue ; } x += 55; cout << (dp[a.size()][x] ? "Possible\n" : "Impossible\n" ); } return 0; } |
ステータス
項目 | データ |
---|---|
問題 | 1217 - Properly Choosing |
ユーザー名 | ei1903 |
投稿日時 | 2019-12-27 09:27:00 |
言語 | C++14 |
状態 | Accepted |
得点 | 10 |
ソースコード長 | 1757 Byte |
最大実行時間 | 72 ms |
最大メモリ使用量 | 17168 KB |
セット
セット | 得点 | Cases | |
---|---|---|---|
1 | ALL | 10 / 10 | in* |
テストケース
ファイル名 | 状態 | 実行時間 | メモリ使用量 | # |
---|---|---|---|---|
in01-01.txt | AC | 18 ms | 604 KB |
1
|
in01-02.txt | AC | 23 ms | 684 KB |
1
|
in01-03.txt | AC | 29 ms | 628 KB |
1
|
in01-04.txt | AC | 27 ms | 1600 KB |
1
|
in01-05.txt | AC | 23 ms | 1548 KB |
1
|
in01-06.txt | AC | 26 ms | 2520 KB |
1
|
in01-07.txt | AC | 69 ms | 3360 KB |
1
|
in01-08.txt | AC | 67 ms | 4328 KB |
1
|
in01-09.txt | AC | 30 ms | 5428 KB |
1
|
in01-10.txt | AC | 27 ms | 6524 KB |
1
|
in01-11.txt | AC | 27 ms | 7496 KB |
1
|
in01-12.txt | AC | 66 ms | 8468 KB |
1
|
in02-01.txt | AC | 18 ms | 8412 KB |
1
|
in02-02.txt | AC | 30 ms | 9652 KB |
1
|
in02-03.txt | AC | 25 ms | 10624 KB |
1
|
in02-04.txt | AC | 27 ms | 10696 KB |
1
|
in02-05.txt | AC | 72 ms | 11664 KB |
1
|
in02-06.txt | AC | 69 ms | 12764 KB |
1
|
in02-07.txt | AC | 70 ms | 13868 KB |
1
|
in02-08.txt | AC | 67 ms | 14968 KB |
1
|
in02-09.txt | AC | 67 ms | 15940 KB |
1
|
in02-10.txt | AC | 68 ms | 17168 KB |
1
|
sample01.txt | AC | 20 ms | 17116 KB | |
sample02.txt | AC | 16 ms | 17072 KB |