結果

問題 No.10 +か×か
ユーザー CleyLCleyL
提出日時 2020-01-21 21:30:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 657 ms / 5,000 ms
コード長 797 bytes
コンパイル時間 689 ms
コンパイル使用メモリ 76,500 KB
実行使用メモリ 389,860 KB
最終ジャッジ日時 2023-08-21 06:28:08
合計ジャッジ時間 3,641 ms
ジャッジサーバーID
(参考情報)
judge14 / judge15
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
162,812 KB
testcase_01 AC 60 ms
163,020 KB
testcase_02 AC 60 ms
162,740 KB
testcase_03 AC 648 ms
389,860 KB
testcase_04 AC 75 ms
164,792 KB
testcase_05 AC 61 ms
162,740 KB
testcase_06 AC 657 ms
386,548 KB
testcase_07 AC 295 ms
234,992 KB
testcase_08 AC 92 ms
171,436 KB
testcase_09 AC 84 ms
167,008 KB
testcase_10 AC 60 ms
162,840 KB
testcase_11 AC 60 ms
162,748 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