結果
問題 |
No.10 +か×か
|
ユーザー |
|
提出日時 | 2024-05-07 00:30:25 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 887 bytes |
コンパイル時間 | 1,951 ms |
コンパイル使用メモリ | 200,092 KB |
最終ジャッジ日時 | 2025-02-21 11:31:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 12 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,S; cin >> N >> S; vector<int> A(N); for(auto &a : A) cin >> a; long long inf = 1e18; vector<long long> dp(S+1,inf); dp.at(A.at(0)) = 0; for(int i=0; i<N-1; i++){ int a = A.at(i+1); vector<long long> next(S+1,inf); for(int k=1; k<=S; k++){ if(dp.at(k) == inf) continue; if(k+a <= S) next.at(k+a) = min(next.at(k+a),dp.at(k)*2); if(k*a <= S) next.at(k*a) = min(next.at(k*a),dp.at(k)*2+1); } swap(dp,next); } long long num = dp.at(S); string answer = ""; for(int i=0; i<N-1; i++){ if(num%2) answer += '*'; else answer += '+'; num /= 2; } reverse(answer.begin(),answer.end()); cout << answer << endl; }