結果
問題 | No.4 おもりと天秤 |
ユーザー |
![]() |
提出日時 | 2022-04-23 20:30:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 5,000 ms |
コード長 | 797 bytes |
コンパイル時間 | 611 ms |
コンパイル使用メモリ | 75,068 KB |
最終ジャッジ日時 | 2025-01-28 21:19:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <iostream> #include <vector> #include <stdbool.h> using namespace std; int N; vector<int> W(1000); vector<bool> memo(10000, false); int sum = 0; int main() { cin >> N; for( int i = 0; i < N; i++ ) { cin >> W[i]; sum += W[i]; } if( sum%2 == 1 ) { cout << "impossible" << endl; return 0; } sum = sum/2; for( int i = 0; i < N; i++ ) { vector<bool> newmemo(10000,false); newmemo[W[i]] = true; for( int j = 0; j < sum; j++ ) { if( memo[j] == true ) { newmemo[j+W[i]] = true; } } for( int j = 0; j <= sum; j++ ) { // cout << j << " " << memo[j] << " " << newmemo[j] << endl; memo[j] = memo[j] | newmemo[j]; } } if( memo[sum] == true ) { cout << "possible" << endl; return 0; } else { cout << "impossible" << endl; } return 0; }