結果
問題 | No.4 おもりと天秤 |
ユーザー |
|
提出日時 | 2017-12-30 22:30:38 |
言語 | C++11 (gcc 4.8.5) |
結果 |
AC
|
実行時間 | 4 ms |
コード長 | 513 Byte |
コンパイル時間 | 944 ms |
使用メモリ | 1,516 KB |
最終ジャッジ日時 | 2019-10-19 08:34:46 |
テストケース
テストケース表示入力 | 結果 | 実行時間 使用メモリ |
---|---|---|
01.txt | AC | 3 ms
1,508 KB |
02.txt | AC | 2 ms
1,496 KB |
03.txt | AC | 2 ms
1,508 KB |
04.txt | AC | 3 ms
1,512 KB |
05.txt | AC | 2 ms
1,508 KB |
06.txt | AC | 3 ms
1,508 KB |
07.txt | AC | 3 ms
1,512 KB |
08.txt | AC | 3 ms
1,512 KB |
09.txt | AC | 3 ms
1,500 KB |
10.txt | AC | 4 ms
1,516 KB |
99_system_test1.txt | AC | 3 ms
1,508 KB |
challenge01.txt | AC | 3 ms
1,512 KB |
challenge02.txt | AC | 3 ms
1,508 KB |
challenge03.txt | AC | 2 ms
1,512 KB |
challenge04.txt | AC | 3 ms
1,508 KB |
challenge05.txt | AC | 3 ms
1,512 KB |
challenge06.txt | AC | 3 ms
1,508 KB |
challenge07.txt | AC | 3 ms
1,512 KB |
challenge08.txt | AC | 3 ms
1,512 KB |
system_test1.txt | AC | 3 ms
1,508 KB |
system_test2.txt | AC | 3 ms
1,508 KB |
system_test3.txt | AC | 4 ms
1,508 KB |
system_test4.txt | AC | 3 ms
1,508 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; int N; int W[110]; bool dp[10010]; int sum = 0; int main() { cin >> N; for (int i = 0; i < N; i++) { cin >> W[i]; sum += W[i]; } if (sum & 1) { cout << "impossible\n"; } else { sum >>= 1; dp[0] = true; for (int i = 0; i < N; i++) { for (int j = sum; j >= 0; j--) { if (j - W[i] < 0) continue; dp[j] |= dp[j - W[i]]; } } cout << (dp[sum] ? "possible" : "impossible") << endl; } return 0; }