結果

問題 No.1872 Dictionary Order
ユーザー srjywrdnprkt
提出日時 2025-03-30 14:28:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 18 ms / 2,000 ms
コード長 1,694 bytes
コンパイル時間 3,752 ms
コンパイル使用メモリ 282,740 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-30 14:28:35
合計ジャッジ時間 5,467 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/modint>

using namespace std;
//using namespace atcoder;
using ll = long long;
//using mint = modint998244353;

int main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    /*
       dp(i, j) = 後ろから見てi番目までで和をjにできるか？

       Pの小さい順に先頭の文字として採用できるかどうかを見る。
       P_iが先頭の数字として採用できるかどうかは
       dp(i+1, M-B_i) = 1かどうかで判定できる。
       次にP_jを先頭の文字として判定できるかどうかは
       MからB_iを引いておくと
       i<jかつdp(j+1, M-B_j)かどうかで判定できる。
    */

    int N, M;
    cin >> N >> M;
    vector<int> p(N+1), a(N+1), q(N+1);
    for (int i=1; i<=N; i++) cin >> a[i];
    for (int i=1; i<=N; i++){
        cin >> p[i];
        q[p[i]] = i;
    }
    vector dp(N+2, vector<bool>(M+1));
    dp[N+1][0] = 1;
    for (int i=N; i>=1; i--){
        for (int j=0; j<=M; j++){
            if (dp[i+1][j] == 1 && j+a[i]<=M) dp[i][j+a[i]] = 1;
            if (dp[i+1][j] == 1) dp[i][j] = 1;
        }
    }

    if (!dp[1][M]){
        cout << -1 << endl;
        return 0;
    }

    vector<int> ans;
    int now=0;
    while(M){
        for (int i=1; i<=N; i++){
            int rev = q[i];
            if (now >= rev) continue;
            if (M-a[rev] >= 0 && dp[rev+1][M-a[rev]]){
                now = rev;
                M -= a[rev];
                ans.push_back(rev);
                break;
            }
        }
    }
    cout << ans.size() << endl;
    for (auto x : ans) cout << x << " ";
    cout << endl;

    return 0;
}
0