結果
問題 |
No.4 おもりと天秤
|
ユーザー |
![]() |
提出日時 | 2019-03-26 04:14:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3 ms / 5,000 ms |
コード長 | 717 bytes |
コンパイル時間 | 1,824 ms |
コンパイル使用メモリ | 193,276 KB |
最終ジャッジ日時 | 2025-01-07 00:29:46 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; const long long MOD = 1000000007; bool dp[10001]; int main() { int n; cin >> n; int a[n]; int sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; sum += a[i]; } dp[0] = true; for (int i = 0; i < n; i++) { for (int j = 10000; j >= 0; j--) { if (dp[j] && dp[i] + j <= 10000) { dp[j + a[i]] = 1; } } } for (int i = 0; i <= 10000; i++) { if (dp[i]) { if (i * 2 == sum) { cout << "possible"; return 0; } } } cout << "impossible"; }