結果
問題 | No.1872 Dictionary Order |
ユーザー |
|
提出日時 | 2022-03-11 21:50:55 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,158 bytes |
コンパイル時間 | 2,745 ms |
コンパイル使用メモリ | 249,920 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-19 08:40:34 |
合計ジャッジ時間 | 5,942 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h> using namespace std; using Line = bitset<2001>; int main() { int N, M; cin >> N >> M; vector<int> A(N); for (int &a : A) cin >> a; vector<int> P(N); for (int &p : P) cin >> p; vector<int> Pinv(N); for (int i = 0; i < N; ++i) Pinv[P[i] - 1] = i; int last_idx = -1; vector<int> ans; for (int i = 0; i < N; ++i) { int p_idx = Pinv[i]; // cout << p_idx << " " << i << " " << M << " " << A[p_idx] << endl; if (p_idx <= last_idx) continue; Line z = 0; z[0] = 1; for (int j = p_idx + 1; j < N; ++j) z |= z << A[j]; // cout << z[1] << " " << z[0] << endl; if (M >= A[p_idx] && z[M - A[p_idx]]) { ans.push_back(p_idx + 1); last_idx = p_idx; M -= A[p_idx]; i = -1; } } if (M != 0) { cout << -1 << endl; assert(ans.empty()); } else { assert(!ans.empty()); cout << ans.size() << endl; for (int x : ans) cout << x << " "; cout << endl; } }