結果
問題 | No.1872 Dictionary Order |
ユーザー |
👑 ![]() |
提出日時 | 2022-03-11 21:45:45 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 22 ms / 2,000 ms |
コード長 | 1,310 bytes |
コンパイル時間 | 875 ms |
コンパイル使用メモリ | 82,632 KB |
最終ジャッジ日時 | 2025-01-28 08:28:16 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <atcoder/modint> using namespace std; using i64 = long long; using m32 = atcoder::static_modint<998244353>; #define rep(i,n) for(int i=0; i<(int)(n); i++) const int INF = 1001001; int main(){ int N,M; cin >> N >> M; vector<int> A(N); rep(i,N) cin >> A[i]; vector<int> P(N); rep(i,N){ cin >> P[i]; P[i]--; } vector<vector<int>> dp(N+1); dp[N] = vector<int>(M+1, INF); dp[N][M] = 0; for(int i=N-1; i>=0; i--){ dp[i] = dp[i+1]; int w = A[i]; for(int p=0; p+w<=M; p++){ if(dp[i+1][p+w] != INF){ if(dp[i][p] == INF || P[i] < P[dp[i][p]]) dp[i][p] = i; } } } if(dp[0][0] == INF){ cout << "-1\n"; } else{ vector<int> ans; int i=0, w=0; while(w != M){ int nx = dp[i][w]; i = nx + 1; w += A[nx]; ans.push_back(nx); } cout << ans.size() << '\n'; rep(j,ans.size()){ if(j) cout << ' '; cout << (ans[j] + 1); } cout << '\n'; } return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } ios_do_not_sync_instance;