結果
問題 |
No.4 おもりと天秤
|
ユーザー |
|
提出日時 | 2017-02-05 18:35:50 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 972 bytes |
コンパイル時間 | 667 ms |
コンパイル使用メモリ | 68,892 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 10:11:50 |
合計ジャッジ時間 | 3,430 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 14 RE * 9 |
ソースコード
#include <iostream> #include <vector> #include <array> #include <algorithm> #include <functional> using namespace std; #define REP(i,first,last) for (int i=first;i<last;i++) int N; int half = 0; vector<int> weights; int dp[100][10000] = {}; bool solve(int idx, int total){ if (dp[idx][total] == 1) return false; if (idx >= N || total > half) return false; int new_total = total + weights[idx]; if (new_total == half) { return true; } else if (solve(idx + 1, total) || solve(idx + 1, new_total)) { return true; } else { dp[idx][total] = 1; return false; } } int main(){ cin >> N; int total = 0; REP(i,0,N){ int val; cin >> val; weights.push_back(val); total += val; } if (total & 1) { cout << "impossible" << endl; } else { half = total >> 1; sort(weights.begin(), weights.end()); if (solve(0,0)) { cout << "possible" << endl; } else { cout << "impossible" << endl; } } }