結果

問題 No.10 ＋か×か
コンテスト
ユーザー wightou
提出日時 2025-05-09 22:47:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 13 ms / 5,000 ms
コード長 1,077 bytes
コンパイル時間 3,515 ms
コンパイル使用メモリ 283,100 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-05-09 22:47:47
合計ジャッジ時間 4,330 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 = "";

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

  vector<vector<bool>> flags(n,vector<bool>(t+1,false));
  flags.at(n-1).at(t) = true;
  for (int i=n-1; i>0; i--) {
    for (int j=0; j<=t; j++) {
      if (!flags.at(i).at(j)) continue;
      if (j>=a.at(i)) flags.at(i-1).at(j-a.at(i)) = true;
      if (j%a.at(i)==0) flags.at(i-1).at(j/a.at(i)) = true;
    }
  }

  int num = a.at(0);
  for (int i=1; i<n; i++) {
    if (num+a.at(i)<=t&&flags.at(i).at(num+a.at(i))) {
      result += '+';
      num += a.at(i);
    } else {
      result += '*';
      num *= a.at(i);
    }
  }

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

  cout << result << endl;

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

  return 0;

}
0