#470117 (C++14) No.1037 exhausted

• 問題: No.1037 exhausted
• ユーザー: sykwer
• 提出日時: 2020-04-25 00:58:09
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 13 ms / 2,000 ms
• コード長: 2,215 bytes
• コンパイル時間: 958 ms
• コンパイル使用メモリ: 116,548 KB
• 実行使用メモリ: 6,820 KB
• 最終ジャッジ日時: 2024-10-15 04:06:34
• 合計ジャッジ時間: 1,775 ms
• ジャッジサーバーID （参考情報）: judge4 / judge3

ファイルパターン	結果
other	AC * 23

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/* ---------- STL Libraries ---------- */
// IO library
#include <cstdio>
#include <fstream>
#include <iomanip>
#include <ios>
#include <iostream>
// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>
#include <random>
#include <cstring>
#include <cassert>
// container library
#include <array>
#include <bitset>
#include <deque>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <vector>
#include <stack>
// type
#include <cstdint>
#include <functional>
/* ---------- Namespace ---------- */
using namespace std;
/* ---------- Type ---------- */
using ll = long long;
#define int ll
template <class T> using MaxHeap = priority_queue<T>;
template <class T> using MinHeap = priority_queue<T, vector<T>, greater<T>>;
#define P pair<ll, ll>
/* ---------- Constants  */
const double PI = 3.141592653589793238462643383279;
const ll MOD = 1e9 + 7;
const int INF = 1LL << 55;
/* ---------- Functions */
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a > b) { a = b; return true; } return false; }
/* v-v-v-v-v-v-v-v-v Main Part v-v-v-v-v-v-v-v-v */
signed main() {
    cin.sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int N, V, L;
    cin >> N >> V >> L;
    vector<int> x(N+2);
    vector<int> f(N+2);
    vector<int> w(N+2);
    for (int i = 1; i <= N ;i++) cin >> x[i] >> f[i] >> w[i];
    x[0] = 0;
    f[0] = 0;
    w[0] = 0;
    x[N+1] = L;
    f[N+1] = 0;
    w[N+1] = 0;
    vector<int> dp1(V+1, INF);
    vector<int> dp2(V+1, INF);
    vector<int> dp3(V+1, INF);
    dp1[V] = 0;
    for (int i = 0; i <= N; i++) {
        int dis = x[i+1] - x[i];
        dp2.assign(V+1, INF);
        for (int v = V; v >= 0; v--) {
            if (v - dis < 0) break;
            dp2[v-dis] = dp1[v];
        }
        dp3 = dp2;
        for (int v = 0; v <= V; v++) {
            chmin(dp3[min(V, v + f[i+1])], dp2[v] + w[i+1]);
        }
        swap(dp1, dp3);
    }
    int ret = INF;
    for (int d : dp1) ret = min(ret, d);
    if (ret == INF) ret = -1;
    cout << ret << endl;
    return 0;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX