結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2019-10-09 01:07:36 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 1,443 bytes |
コンパイル時間 | 2,128 ms |
コンパイル使用メモリ | 200,000 KB |
最終ジャッジ日時 | 2025-01-07 21:21:12 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <bits/stdc++.h>#define loop(n) for (int ngtkana_is_genius = 0; ngtkana_is_genius < int(n); ngtkana_is_genius++)#define rep(i, begin, end) for(int i = int(begin); i < int(end); i++)#define all(v) v.begin(), v.end()#define rand(l, r) std::uniform_int_distribution<>(l, r)(mt)using lint = long long;auto cmn = [](auto& a, auto b){if (a > b) {a = b; return true;} return false;};auto cmx = [](auto& a, auto b){if (a < b) {a = b; return true;} return false;};void err() { std::cout << -1 << std::endl; exit(0); }#define require(exp) do { if (!(exp)) { err(); } } while(false)int main() {std::cin.tie(0); std::cin.sync_with_stdio(false);int n, V, L;std::cin >> n >> V >> L;std::vector< int > x(n), v(n), w(n);rep(i, 0, n) {std::cin >> x.at(i) >> v.at(i) >> w.at(i);}x.push_back(L);v.push_back(0);w.push_back(0);// errorif (V < x.front()){ err(); }rep(i, 0, n) {if (V < x.at(i + 1) - x.at(i)){ err(); }}constexpr lint linf = 1LL << 60;std::vector< lint > dp(V + L + 1, linf);dp.at(V) = 0;auto time = 0;rep(i, 0, n + 1) {auto s = x.at(i), t = s + V;for (auto j = t; j >= s; j--) {if (dp.at(j) == linf) continue;auto k = std::min(t, j + v.at(i));cmn(dp.at(k), dp.at(j) + w.at(i));}}auto ret = *std::min_element(dp.begin() + L, dp.end());if (ret == linf) err();std::cout << ret << std::endl;return 0;}