結果
問題 | No.10 +か×か |
ユーザー | kroton |
提出日時 | 2014-11-01 04:41:47 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 129 ms / 5,000 ms |
コード長 | 1,048 bytes |
コンパイル時間 | 438 ms |
コンパイル使用メモリ | 55,264 KB |
実行使用メモリ | 177,912 KB |
最終ジャッジ日時 | 2023-08-21 06:08:12 |
合計ジャッジ時間 | 2,092 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 62 ms
175,340 KB |
testcase_01 | AC | 63 ms
175,484 KB |
testcase_02 | AC | 62 ms
175,372 KB |
testcase_03 | AC | 106 ms
177,812 KB |
testcase_04 | AC | 64 ms
175,680 KB |
testcase_05 | AC | 62 ms
175,496 KB |
testcase_06 | AC | 129 ms
177,912 KB |
testcase_07 | AC | 81 ms
175,900 KB |
testcase_08 | AC | 65 ms
176,040 KB |
testcase_09 | AC | 69 ms
176,336 KB |
testcase_10 | AC | 62 ms
175,444 KB |
testcase_11 | AC | 63 ms
175,508 KB |
ソースコード
#include <iostream> using namespace std; const string dame = "dame"; bool done[55][100010]; string dp[55][100010]; int N, total, A[55]; string solve(int k, int acc){ if(k >= N){ if(acc == total){ return ""; } else { return dame; } } if(acc > total)return dame; if(done[k][acc])return dp[k][acc]; { string next = solve(k + 1, acc + A[k]); if(next != dame){ string res = "+" + next; done[k][acc] = true; return dp[k][acc] = res; } } { string next = solve(k + 1, acc * A[k]); if(next != dame){ string res = "*" + next; done[k][acc] = true; return dp[k][acc] = res; } } done[k][acc] = true; return dp[k][acc] = dame; } int main(){ cin >> N >> total; for(int i=0;i<N;i++)cin >> A[i]; cout << solve(1, A[0]) << endl; return 0; }