結果
問題 | No.1872 Dictionary Order |
ユーザー |
|
提出日時 | 2021-11-21 16:12:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,014 bytes |
コンパイル時間 | 3,097 ms |
コンパイル使用メモリ | 202,124 KB |
最終ジャッジ日時 | 2025-01-26 00:02:39 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 WA * 1 |
other | AC * 14 WA * 18 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, M; cin >> N >> M; vector<int> A(N); for (int i = 0; i < N; ++i) cin >> A[i]; vector<vector<bool>> dp(N + 1, vector<bool>(M + 1, false)); dp[N][0] = true; for (int i = N - 1; i >= 0; --i) { for (int j = 0; j <= M; ++j) dp[i][j] = dp[i + 1][j]; for (int j = A[i]; j <= M; ++j) dp[i][j] = dp[i][j] || dp[i + 1][j - A[i]]; } if (!dp[0][M]) { puts("-1"); return 0; } vector<int> P(N); for (int i = 0; i < N; ++i) { int a; cin >> a; P[a - 1] = i; } int sum = M; vector<int> ans{-1}; for (int i = 0; i < N; ++i) { if (ans.back() >= P[i]) continue; if (sum >= A[P[i]] && dp[P[i]][sum] && dp[P[i] + 1][sum - A[P[i]]]) { ans.push_back(P[i]); sum -= A[P[i]]; } } cout << ans.size() - 1 << endl; for (int i = 1; i < ans.size(); ++i) cout << ans[i] + 1 << " \n"[i == ans.size() - 1]; }