結果
問題 | 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 r struct 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 l struct 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; }