結果
問題 |
No.10 +か×か
|
ユーザー |
|
提出日時 | 2024-10-21 02:24:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 9 ms / 5,000 ms |
コード長 | 879 bytes |
コンパイル時間 | 2,230 ms |
コンパイル使用メモリ | 203,456 KB |
最終ジャッジ日時 | 2025-02-24 22:07:16 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define ll long long int main(){ cin.tie(nullptr)->sync_with_stdio(false); ll N, T; cin >> N >> T; vector A(N, 0ll); for(auto& x: A) cin >> x; vector dp(N + 1, vector(T + 1, false)); dp[N][T] = true; for(int i = N - 1; i >= 0; --i){ for(int t = 1; t <= T; ++t) if(dp[i + 1][t]){ if(0 <= t - A[i]) dp[i][t - A[i]] = true; if(t % A[i] == 0) dp[i][t / A[i]] = true; } } if(!dp[0][0]) cout << -1; else{ string ans = ""; ll s = A[0]; for(int i = 1; i < N; ++i){ if(s + A[i] <= T && dp[i + 1][s + A[i]]){ ans += '+'; s += A[i]; continue; } if(s * A[i] <= T && dp[i + 1][s * A[i]]){ ans += '*'; s *= A[i]; continue; } assert(false); } assert(s == T); cout << ans; } cout << endl; return 0; }