結果
問題 | No.1037 exhausted |
ユーザー |
|
提出日時 | 2020-04-24 22:34:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 45 ms / 2,000 ms |
コード長 | 1,680 bytes |
コンパイル時間 | 2,456 ms |
コンパイル使用メモリ | 199,524 KB |
最終ジャッジ日時 | 2025-01-10 00:09:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h> // clang-format offusing Int = long long;#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;#ifndef _MY_DEBUG#define dump(...)#endif // clang-format on/*** author: knshnb* created: Fri Apr 24 22:20:28 JST 2020**/template <class T> inline bool chmin(T& a, const T& b) {if (a <= b) return false;a = b;return true;}template <class T> inline bool chmax(T& a, const T& b) {if (a >= b) return false;a = b;return true;}template <class T, class S> T make_vec(S x) { return x; }template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {return std::vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));}const Int INF = 1e18;signed main() {Int n, V, L;std::cin >> n >> V >> L;std::vector<Int> x(n + 2), v(n + 2), w(n + 2);REP(i, 1, n + 1) std::cin >> x[i] >> v[i] >> w[i];x.back() = L;auto dp = make_vec<Int>(n + 2, V + 2, INF);REP(j, V + 1) dp[0][j] = 0;REP(i, 1, n + 2) {Int dif = x[i] - x[i - 1];dump(dif);for (Int j = V; j >= 0; j--) {if (j + dif <= V) chmin(dp[i][j], dp[i - 1][j + dif]);}for (Int j = V; j >= 0; j--) {if (j - v[i] >= 0) chmin(dp[i][j], dp[i][j - v[i]] + w[i]);chmin(dp[i][j], dp[i][j + 1]);}}std::cout << (dp[n + 1][0] == INF ? -1 : dp[n + 1][0]) << std::endl;}