結果
問題 | No.1037 exhausted |
ユーザー | yuruhiya |
提出日時 | 2020-04-29 19:49:46 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 9 ms / 2,000 ms |
コード長 | 2,711 bytes |
コンパイル時間 | 747 ms |
コンパイル使用メモリ | 57,520 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-29 16:01:03 |
合計ジャッジ時間 | 1,503 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,248 KB |
testcase_02 | AC | 2 ms
5,248 KB |
testcase_03 | AC | 2 ms
5,248 KB |
testcase_04 | AC | 2 ms
5,248 KB |
testcase_05 | AC | 2 ms
5,248 KB |
testcase_06 | AC | 2 ms
5,248 KB |
testcase_07 | AC | 2 ms
5,248 KB |
testcase_08 | AC | 2 ms
5,248 KB |
testcase_09 | AC | 2 ms
5,248 KB |
testcase_10 | AC | 2 ms
5,248 KB |
testcase_11 | AC | 2 ms
5,248 KB |
testcase_12 | AC | 9 ms
5,248 KB |
testcase_13 | AC | 9 ms
5,248 KB |
testcase_14 | AC | 9 ms
5,248 KB |
testcase_15 | AC | 9 ms
5,248 KB |
testcase_16 | AC | 9 ms
5,248 KB |
testcase_17 | AC | 9 ms
5,248 KB |
testcase_18 | AC | 8 ms
5,248 KB |
testcase_19 | AC | 9 ms
5,248 KB |
testcase_20 | AC | 3 ms
5,248 KB |
testcase_21 | AC | 2 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
ソースコード
#pragma GCC optimize ("O3") #pragma GCC target ("avx") //#pragma GCC optimize ("Ofast") #include <cstdio> #include <cctype> #include <algorithm> #include <vector> #include <utility> using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) #define FOR(i, m, n) for (int i = (m); i < (n); ++i) #define rrep(i, n) for (int i = (n) - 1; i >= 0; --i) #define rfor(i, m, n) for (int i = (m); i >= (n); --i) using ll = long long; #ifdef _WIN32 #define gc _getchar_nolock #define pc _putchar_nolock #else #define gc getchar_unlocked #define pc putchar_unlocked #endif #if __has_include("dump.hpp") #include "dump.hpp" #else #define dump(...) ((void)0) #endif inline void inui(int& v)noexcept { v = 0; for (char c = gc(); isdigit(c); c = gc()) v = v * 10 + (c - '0'); } inline void inul(ll& v)noexcept { v = 0; for (char c = gc(); isdigit(c); c = gc()) v = v * 10 + (c - '0'); } inline void ini(int& v)noexcept { v = 0; char c = gc(); bool f = false; if (c == '-') { f = true; c = gc(); } for (; isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (f)v = -v; } inline void inl(ll& v)noexcept { v = 0; char c = gc(); bool f = false; if (c == '-') { f = true; c = gc(); } for (; isdigit(c); c = gc()) v = v * 10 + (c - '0'); if (f)v = -v; } inline void ins(char* c, int n)noexcept { while (n--) { *c = gc(); ++c; } } inline void outi(int v)noexcept { if (v < 0)pc('-'), v = -v; char b[10]; int n = 0; while (v)b[n++] = '0' + v % 10, v /= 10; if (!n)b[n++] = '0'; while (n--)pc(b[n]); } inline void outui(int v)noexcept { char b[10]; int n = 0; while (v)b[n++] = '0' + v % 10, v /= 10; if (!n)b[n++] = '0'; while (n--)pc(b[n]); } inline void outl(ll v)noexcept { if (v < 0)pc('-'), v = -v; char b[20]; int n = 0; while (v)b[n++] = '0' + v % 10, v /= 10; if (!n)b[n++] = '0'; while (n--)pc(b[n]); } inline void outul(ll v)noexcept { char b[20]; int n = 0; while (v)b[n++] = '0' + v % 10, v /= 10; if (!n)b[n++] = '0'; while (n--)pc(b[n]); } constexpr int MAX_N = 2005, MAX_V = 2005; constexpr ll inf = 1e16; int N, V, L; int x[MAX_N], v[MAX_N]; ll w[MAX_N], dp[MAX_V + 1]; int main() { inui(N); inui(V); inui(L); rep(i, N) { inui(x[i + 1]); inui(v[i + 1]); inul(w[i + 1]); } x[N + 1] = L; N += 2; rep(i, V)dp[i] = inf; FOR(i, 1, N) { int dist = x[i] - x[i - 1]; if (dist > V) { puts("-1"); return 0; } rep(i, V + 1 - dist) { dp[i] = dp[i + dist]; } FOR(i, V + 1 - dist, V + 1) { dp[i] = inf; } rrep(j, V + 1) { int k = min(V, j + v[i]); dp[k] = min(dp[k], dp[j] + w[i]); } } ll ans = inf; rep(i, V + 1) { if (ans > dp[i]) ans = dp[i]; } if (ans != inf) { outul(ans); pc('\n'); } else { puts("-1"); } }