結果
問題 | No.10 +か×か |
ユーザー | y_mazun |
提出日時 | 2015-04-17 03:13:21 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 10 ms / 5,000 ms |
コード長 | 771 bytes |
コンパイル時間 | 431 ms |
コンパイル使用メモリ | 64,264 KB |
実行使用メモリ | 20,108 KB |
最終ジャッジ日時 | 2023-08-21 06:12:20 |
合計ジャッジ時間 | 1,203 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 2 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 10 ms
18,224 KB |
testcase_04 | AC | 8 ms
20,108 KB |
testcase_05 | AC | 5 ms
20,016 KB |
testcase_06 | AC | 10 ms
18,256 KB |
testcase_07 | AC | 8 ms
18,120 KB |
testcase_08 | AC | 4 ms
11,876 KB |
testcase_09 | AC | 5 ms
11,928 KB |
testcase_10 | AC | 2 ms
5,632 KB |
testcase_11 | AC | 2 ms
5,632 KB |
ソースコード
#include <iostream> #define REP(i,n) for(int i=0; i<(int)(n); i++) #include <queue> #include <cstdio> inline int getInt(){ int s; scanf("%d", &s); return s; } #include <set> using namespace std; int dp[51][100000]; int main(){ const int n = getInt(); const int t = getInt(); vector<int> a(n); REP(i,n) a[i] = getInt(); dp[n][t] = 1; for(int i = n - 1; i >= 0; i--){ REP(j,t+1) if(dp[i + 1][j]){ if(j - a[i] >= 0) dp[i][j - a[i]] = 1; if(j % a[i] == 0) dp[i][j / a[i]] = 1; } } string ans(n - 1, '*'); int cur = a[0]; REP(i,n-1){ if(dp[i + 2][cur + a[i + 1]]){ cur += a[i + 1]; ans[i] = '+'; }else{ cur *= a[i + 1]; ans[i] = '*'; } } puts(ans.c_str()); return 0; }