結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2022-02-16 03:35:15 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 1,275 bytes |
コンパイル時間 | 4,821 ms |
コンパイル使用メモリ | 143,632 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2024-06-29 07:11:42 |
合計ジャッジ時間 | 5,055 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <cassert>#include <cmath>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;int main() {ll N, VL, L;cin >> N >> VL >> L;vector<ll> X(N + 2);vector<ll> V(N + 2);vector<ll> W(N + 2);X[0] = 0;V[0] = 0;W[0] = 0;for (int i = 1; i <= N; ++i) {cin >> X[i] >> V[i] >> W[i];}X[N + 1] = L;V[N + 1] = 0;W[N + 1] = 0;vector<vector<ll>> dp(N + 2, vector<ll>(VL + 1, LLONG_MAX));dp[0][VL] = 0;for (int i = 0; i <= N; ++i) {int dist = X[i + 1] - X[i];for (int v = VL; v >= 0; --v) {if (dp[i][v] == LLONG_MAX) continue;int nv = v - dist;if (nv < 0) break;dp[i + 1][nv] = min(dp[i + 1][nv], dp[i][v]);ll cv = min(VL, nv + V[i + 1]);dp[i + 1][cv] = min(dp[i + 1][cv], dp[i + 1][nv] + W[i + 1]);}for (int v = VL - 1; v >= 0; --v) {dp[i + 1][v] = min(dp[i + 1][v], dp[i + 1][v + 1]);}}ll ans = LLONG_MAX;for (int v = 0; v <= VL; ++v) {ans = min(ans, dp[N + 1][v]);}if (ans == LLONG_MAX) {cout << -1 << endl;} else {cout << ans << endl;}return 0;}