結果
問題 | No.1037 exhausted |
ユーザー |
![]() |
提出日時 | 2020-04-24 22:31:08 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 42 ms / 2,000 ms |
コード長 | 2,345 bytes |
コンパイル時間 | 1,036 ms |
コンパイル使用メモリ | 118,044 KB |
実行使用メモリ | 34,688 KB |
最終ジャッジ日時 | 2024-10-15 03:12:12 |
合計ジャッジ時間 | 2,146 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
#include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>#include <vector>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <queue>#include <ctime>#include <cassert>#include <complex>#include <string>#include <cstring>#include <chrono>#include <random>#include <queue>#include <bitset>#include <stack>#include <functional>#ifdef LOCAL#define eprintf(...) fprintf(stderr, __VA_ARGS__)#else#define eprintf(...) 42#endif#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)#define all(x) (x).begin(), (x).end()template <class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }template <class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; }// template <class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }using namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair <int,int> P;typedef long double ld;struct stand {int x, v, w;};const ll INF = 1e15;int main (void){cin.tie(0);ios::sync_with_stdio(false);int n, v, l; cin >> n >> v >> l;vector<stand> a(n); for (auto &e : a) cin >> e.x >> e.v >> e.w;a.push_back({l, 0, 0});vector<vector<ll>> dp (n + 2, vector<ll>(v + 1));rep (i, dp.size()) rep (j, dp[0].size()) dp[i][j] = INF;dp[0][v] = 0;rep (i, n + 1) {reprev (j, v + 1) {if (j - a[i].x + (i == 0 ? 0LL : a[i - 1].x) < 0) break;// eprintf("%d %d %d\n", a[i].x, i, j);dp[i + 1][j - a[i].x + (i == 0 ? 0LL : a[i - 1].x)] = dp[i][j];}reprev (j, v + 1) {chmin(dp[i + 1][min(v, j + a[i].v)], dp[i + 1][j] + a[i].w);}}ll ans = INF;rep (j, v + 1) {rep (i, n + 2) eprintf("%3lld ", (dp[i][j] >= INF ? -1 : dp[i][j])); eprintf("\n");// rep (i, n + 2) eprintf("%3lld ", dp[i][j]); eprintf("\n");}rep (i, v + 1) chmin(ans, dp[n + 1][i]);cout << (ans >= INF ? -1 : ans) << '\n';return 0;}