結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2020-04-24 21:50:48 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 46 ms / 2,000 ms |
コード長 | 2,633 bytes |
コンパイル時間 | 1,018 ms |
コンパイル使用メモリ | 81,368 KB |
最終ジャッジ日時 | 2025-01-09 23:32:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:80:36: warning: narrowing conversion of ‘(N + 2)’ from ‘int’ to ‘std::size_t’ {aka ‘long unsigned int’} [-Wnarrowing] 80 | auto dp = gen_vec<long long>({ N + 2, V + 1 }, inf); | ~~^~~ main.cpp:80:43: warning: narrowing conversion of ‘(V + 1)’ from ‘int’ to ‘std::size_t’ {aka ‘long unsigned int’} [-Wnarrowing] 80 | auto dp = gen_vec<long long>({ N + 2, V + 1 }, inf); | ~~^~~
ソースコード
#include <iostream>#include <algorithm>#include <utility>#include <vector>#include <numeric>template <class T, class U>inline bool chmin(T &lhs, const U &rhs) {if (lhs > rhs) {lhs = rhs;return true;}return false;}template <class T, class U>inline bool chmax(T &lhs, const U &rhs) {if (lhs < rhs) {lhs = rhs;return true;}return false;}// [l, r) from l to rstruct range {struct itr {int i;constexpr itr(int i_): i(i_) { }constexpr void operator ++ () { ++i; }constexpr int operator * () const { return i; }constexpr bool operator != (itr x) const { return i != x.i; }};const itr l, r;constexpr range(int l_, int r_): l(l_), r(std::max(l_, r_)) { }constexpr itr begin() const { return l; }constexpr itr end() const { return r; }};// [l, r) from r to lstruct revrange {struct itr {int i;constexpr itr(int i_): i(i_) { }constexpr void operator ++ () { --i; }constexpr int operator * () const { return i; }constexpr bool operator != (itr x) const { return i != x.i; }};const itr l, r;constexpr revrange(int l_, int r_): l(l_ - 1), r(std::max(l_, r_) - 1) { }constexpr itr begin() const { return r; }constexpr itr end() const { return l; }};template <class T, std::size_t N, std::size_t I = 0>auto gen_vec(const std::size_t (&list)[N], typename std::enable_if<(I == N), const T&>::type value = T()) {return value;}template <class T, std::size_t N, std::size_t I = 0>auto gen_vec(const std::size_t (&list)[N], typename std::enable_if<(I != N), const T&>::type value = T()) {return std::vector<decltype(gen_vec<T, N, I + 1>(list, value))>(list[I], gen_vec<T, N, I + 1>(list, value));}constexpr long long inf = (1ll << 60);int main() {int N, V, L;std::cin >> N >> V >> L;std::vector<int> x(N + 2), v(N + 1), w(N + 1);x.back() = L;for (int i: range(1, N + 1)) {std::cin >> x[i] >> v[i] >> w[i];}std::vector<int> c(N + 1);for (int i: range(0, N + 1)) {c[i] = x[i + 1] - x[i];}auto dp = gen_vec<long long>({ N + 2, V + 1 }, inf);dp[0][V] = 0;for (int i: range(0, N + 1)) {for (int j: range(0, V + 1)) {{int nj = std::min(V, j + v[i]) - c[i];if (nj >= 0) {chmin(dp[i + 1][nj], dp[i][j] + w[i]);}}{int nj = j - c[i];if (nj >= 0) {chmin(dp[i + 1][nj], dp[i][j]);}}}}long long ans = inf;for (int i: range(0, V + 1)) {chmin(ans, dp[N + 1][i]);}std::cout << (ans == inf ? -1 : ans) << '\n';return 0;}