結果

問題 No.10 ＋か×か
ユーザー wightou
提出日時 2025-05-09 22:12:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 3,818 ms / 5,000 ms
コード長 1,208 bytes
コンパイル時間 3,619 ms
コンパイル使用メモリ 289,788 KB
実行使用メモリ 37,504 KB
最終ジャッジ日時 2025-05-09 22:13:12
合計ジャッジ時間 12,773 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

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

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

  int n, t;
  cin >> n >> t;

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

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

  string result = "";

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

  set<pair<string,int>> s;
  for (int num : a) {
    if (s.empty()) {
      s.emplace("",num);
      continue;
    }
    set<pair<string,int>> next;
    set<int> check;
    for (auto [str,i] : s) {
      if (check.find(i+num)==check.end()&&i+num<=t) {
        check.emplace(i+num);
        next.emplace(str+'a',i+num);
      }
      if (check.find(i*num)==check.end()&&i*num<=t) {
        check.emplace(i*num);
        next.emplace(str+'b',i*num);
      }
    }
    swap(s,next);
  }

  for (auto [str,i] : s) {
    if (i==t) {
      for (char c : str) {
        if (c=='a') result += '+';
        else if (c=='b') result += '*';
      }
      break;
    }
  }

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

  cout << result << endl;

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

  return 0;

}
0