結果

問題 No.10 ＋か×か
ユーザー 👑 CleyLCleyL
提出日時 2020-01-21 21:30:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 663 ms / 5,000 ms
コード長 797 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 76,772 KB
実行使用メモリ 390,140 KB
最終ジャッジ日時 2024-05-08 12:00:03
合計ジャッジ時間 3,671 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
162,836 KB
testcase_01 AC 61 ms
162,968 KB
testcase_02 AC 61 ms
162,856 KB
testcase_03 AC 663 ms
390,140 KB
testcase_04 AC 76 ms
164,864 KB
testcase_05 AC 60 ms
162,676 KB
testcase_06 AC 655 ms
386,620 KB
testcase_07 AC 304 ms
235,068 KB
testcase_08 AC 94 ms
171,452 KB
testcase_09 AC 84 ms
167,132 KB
testcase_10 AC 61 ms
162,700 KB
testcase_11 AC 62 ms
162,960 KB
権限があれば一括ダウンロードができます

ソースコード

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