結果
問題 | No.15 カタログショッピング |
ユーザー |
|
提出日時 | 2022-10-21 01:19:13 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,045 bytes |
コンパイル時間 | 1,995 ms |
コンパイル使用メモリ | 203,148 KB |
最終ジャッジ日時 | 2025-02-08 09:30:29 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 5 TLE * 4 MLE * 1 |
ソースコード
#include <bits/stdc++.h> #define rep(i,n) for(int i = 0; i < (n); i++) using namespace std; typedef long long ll; int main(){ cin.tie(0); ios::sync_with_stdio(0); int N,S; cin >> N >> S; vector<int> P(N); rep(i,N) cin >> P[i]; vector<vector<bool>> dp(N + 1, vector<bool>(S + 1, 0)); dp[N][S] = true; for(int i = N - 1; i >= 0; i--) { for(int s = 0; s <= S; s++) { if(0 <= s - P[i] && dp[i + 1][s]) dp[i][s - P[i]] = true; if(dp[i + 1][s]) dp[i][s] = true; } } vector<int> ans; function<void(int,int)> dfs = [&](int i, int sum) -> void { if(i == N) { rep(j,(int)ans.size()) cout << ans[j] << " \n"[j == int(ans.size()) - 1]; } else { if(sum + P[i] <= S && dp[i + 1][sum + P[i]]) { ans.push_back(i + 1); dfs(i + 1, sum + P[i]); ans.pop_back(); } if(dp[i + 1][sum]) { dfs(i + 1, sum); } } }; dfs(0, 0); }