結果

問題 No.4 おもりと天秤
コンテスト
ユーザー wightou
提出日時 2025-06-27 04:05:20
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 838 bytes
コンパイル時間 3,029 ms
コンパイル使用メモリ 281,932 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-27 04:05:25
合計ジャッジ時間 4,191 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

/////////////////// メイン ///////////////////

int main () {
  
  //////////////////// 入力 ////////////////////

  int n;
  cin >> n;

  vector<int> a(n);
  for (int i=0; i<n; i++) {
    cin >> a.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  string result = "impossible";

  //////////////////// 処理 ////////////////////

  int sum = accumulate(a.begin(),a.end(),0);

  if (sum%2==0) {

    vector<bool> dp(sum/2+1,false);
    dp.at(0) = true;

    for (int w : a) {
      for (int i=sum/2-w; i>=0; i--) {
        dp.at(i+w) = dp.at(i+w)|dp.at(i);
      }
    }

    if (dp.at(sum/2)) result = "possible";

  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}
0