結果
問題 | No.10 +か×か |
ユーザー | ktg |
提出日時 | 2016-04-23 21:44:45 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 799 ms / 5,000 ms |
コード長 | 1,730 bytes |
コンパイル時間 | 639 ms |
コンパイル使用メモリ | 66,180 KB |
実行使用メモリ | 334,284 KB |
最終ジャッジ日時 | 2023-08-21 06:18:22 |
合計ジャッジ時間 | 4,169 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 69 ms
175,244 KB |
testcase_01 | AC | 68 ms
175,216 KB |
testcase_02 | AC | 68 ms
175,204 KB |
testcase_03 | AC | 799 ms
334,284 KB |
testcase_04 | AC | 120 ms
176,556 KB |
testcase_05 | AC | 116 ms
175,272 KB |
testcase_06 | AC | 773 ms
328,356 KB |
testcase_07 | AC | 289 ms
220,940 KB |
testcase_08 | AC | 140 ms
185,220 KB |
testcase_09 | AC | 126 ms
182,960 KB |
testcase_10 | AC | 72 ms
175,264 KB |
testcase_11 | AC | 71 ms
175,268 KB |
ソースコード
//#include <algorithm> //#include <cmath> //#include <cstring> #include <iostream> #include <map> #include <numeric> //#include <queue> //#include <set> //#include <sstream> //#include <stack> #include <string> #include <vector> #include <iterator> //#define pb push_back //#define puts(x) cout << #x << " : " << x << endl; //#pragma GCC diagnostic ignored "-Wconversion" //#define REP(i,n) for (int i=0;i<(n);i++) //#define REPE(i,n) for (int i=0;i<=(n);i++) //#define init(a,b) memset((a), (b), (sizeof(a))); //#define PI 3.14159265 //#define EPS (1e-10) //#define EQ(a,b) (abs((a)-(b)) < EPS) using namespace std; //typedef long long ll; //#define int long long typedef pair<int, int> P; string dp[55][100005]; int a[55]; signed main() { int n; int total; cin>>n>>total; for(int i=0;i<n;i++)cin>>a[i]; for(int i=0;i<n;i++){ fill(dp[i], dp[i] + 100005, ""); } dp[0][0]="0"; for(int i=0;i<n;i++){ for(int j=0;j<=100000;j++){ if(!dp[i][j].empty()){ int plus = j + a[i]; int mul = j * a[i]; string s1 = dp[i][j] + "0"; string s2 = dp[i][j] + "1"; if(plus <= total){ if(dp[i+1][plus].empty() || dp[i + 1][plus] > s1){ dp[i+1][plus] = s1; } } if(mul <= total){ if (dp[i+1][mul].empty() || dp[i+1][mul] > s2){ dp[i+1][mul] = s2; } } } } } for(int i=2;i<dp[n][total].size();i++){ if(dp[n][total][i]=='0')cout<<'+'; else cout<<'*'; } cout<<endl; return 0; }