結果
問題 | No.10 +か×か |
ユーザー | なお |
提出日時 | 2014-10-05 18:19:12 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 671 ms / 5,000 ms |
コード長 | 1,137 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 55,504 KB |
実行使用メモリ | 468,144 KB |
最終ジャッジ日時 | 2023-08-21 06:07:57 |
合計ジャッジ時間 | 4,233 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 186 ms
319,024 KB |
testcase_01 | AC | 128 ms
319,016 KB |
testcase_02 | AC | 125 ms
318,896 KB |
testcase_03 | AC | 671 ms
468,144 KB |
testcase_04 | AC | 139 ms
323,896 KB |
testcase_05 | AC | 130 ms
319,204 KB |
testcase_06 | AC | 666 ms
466,780 KB |
testcase_07 | AC | 312 ms
367,080 KB |
testcase_08 | AC | 160 ms
326,992 KB |
testcase_09 | AC | 150 ms
324,500 KB |
testcase_10 | AC | 126 ms
319,016 KB |
testcase_11 | AC | 129 ms
319,096 KB |
ソースコード
#include <stdlib.h> #include <iostream> #include <string> using namespace std; #define REP(i, n) for(int(i)=0;(i)<(n);++(i)) bool dp1[101][100010]; string dp2[101][100010]; int main(){ int N, total, A; cin >> N >> total; REP(i,N+1) REP(j,total+1) dp1[i][j] = false; cin >> A; dp1[0][A] = true; REP(i,N-1){ cin >> A; for(int j = 0; j <= total; j++){ if(!dp1[i][j]) continue; int k = j + A; if(k <= total){ string ks = dp2[i][j] + "0"; dp1[i+1][k] = true; if(dp2[i+1][k] == "" || dp2[i+1][k] > ks) dp2[i+1][k] = ks; } int l = j * A; if(l <= total){ string ls = dp2[i][j] + "1"; dp1[i+1][l] = true; if(dp2[i+1][l] == "" || dp2[i+1][l] > ls) dp2[i+1][l] = ls; } } } string res = dp2[N-1][total]; if(res != ""){ REP(i,res.size()){ if(res[i] == '0') res[i] = '+'; if(res[i] == '1') res[i] = '*'; } cout << res << endl; } return 0; }