結果
問題 |
No.1037 exhausted
|
ユーザー |
![]() |
提出日時 | 2020-04-24 22:29:12 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 2,000 ms |
コード長 | 1,319 bytes |
コンパイル時間 | 3,132 ms |
コンパイル使用メモリ | 199,848 KB |
最終ジャッジ日時 | 2025-01-10 00:05:38 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { constexpr int64_t inf = 1e18; int n, vmax, l; cin >> n >> vmax >> l; vector<int> x(n + 2), v(n + 2), w(n + 2); for (int i = 0; i < n; i++) { cin >> x.at(i + 1) >> v.at(i + 1) >> w.at(i + 1); } x.at(n + 1) = l; vector<vector<int64_t>> dp(n + 2, vector<int64_t>(vmax + 1, inf)); // remaining, cost dp.at(0).at(vmax) = 0; for (int i = 0; i <= n; i++) { int used = x.at(i + 1) - x.at(i); for (int j = 0; j <= vmax; j++) { int prev_j = j + used, prev_j_stop = prev_j - v.at(i + 1); if (prev_j <= vmax) { dp.at(i + 1).at(j) = min(dp.at(i + 1).at(j), dp.at(i).at(prev_j)); } if (prev_j_stop >= used && prev_j_stop <= vmax) { dp.at(i + 1).at(j) = min(dp.at(i + 1).at(j), dp.at(i).at(prev_j_stop) + w.at(i + 1)); } } for (int j = vmax + used - v.at(i + 1); j <= vmax; j++) { dp.at(i + 1).at(vmax) = min(dp.at(i + 1).at(vmax), dp.at(i).at(j) + w.at(i + 1)); } } int64_t ans = inf; for (int i = 0; i <= vmax; i++) { ans = min(ans, dp.at(n + 1).at(i)); } if (ans == inf) { cout << -1 << endl; } else { cout << ans << endl; } }