結果
問題 | 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, costdp.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;}}