結果

問題 No.10 ＋か×か
コンテスト
ユーザー 👑 CleyL
提出日時 2020-01-21 21:30:17
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 669 ms / 5,000 ms
コード長 797 bytes
コンパイル時間 757 ms
コンパイル使用メモリ 76,828 KB
実行使用メモリ 389,992 KB
最終ジャッジ日時 2024-12-14 15:43:50
合計ジャッジ時間 3,618 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
string dp[51][100010];
string comin(string A,string B){//A.size == B.size が前提
  if(A.empty())return B;
  if(B.empty())return A;
  for(int i = 0; A.size() > i; i++){
    if(A[i] == '+' && B[i] == '*')return A;
    if(A[i] == '*' && B[i] == '+')return B;
  }
  return A;
}
int main(){
  int N,T;cin>>N>>T;
  int A[N];
  for(int i = 0; N > i; i++){
    cin>>A[i];
  }
  dp[0][A[0]] = '!';
  for(int i = 1; N > i; i++){
    for(int j = 0; T >= j; j++){
      if(dp[i-1][j].empty())continue;
      if(j+A[i] <= T)dp[i][j+A[i]] = comin(dp[i][j+A[i]],dp[i-1][j] + "+");
      if(j*A[i] <= T)dp[i][j*A[i]] = comin(dp[i][j*A[i]],dp[i-1][j] + "*");
    }
  }
  cout << dp[N-1][T].substr(1,N-1) << endl;
}
0