結果
問題 | No.844 split game |
ユーザー |
![]() |
提出日時 | 2019-06-28 21:49:25 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 54 ms / 2,000 ms |
コード長 | 2,510 bytes |
コンパイル時間 | 1,622 ms |
コンパイル使用メモリ | 174,968 KB |
実行使用メモリ | 9,728 KB |
最終ジャッジ日時 | 2024-07-02 04:36:58 |
合計ジャッジ時間 | 4,495 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 56 |
ソースコード
// #define DEBUGGING #include <bits/stdc++.h> using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template <typename T> using V = vector<T>; template <typename T> using VV = V<V<T>>; template <typename T, typename U> using P = pair<T, U>; using ll = int64_t; using PLL = P<ll, ll>; template <typename T> const T& var_min(const T &t) { return t; } template <typename T> const T& var_max(const T &t) { return t; } template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template <typename T> void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } #ifdef DEBUGGING #include "../debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif template <typename T> T make_v(T init) { return init; } template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { #define rec make_v(init, tail...) return V<decltype(rec)>(s, rec); #undef rec } int main() { ll N, M, A; cin >> N >> M >> A; VV<PLL> rp(1e5 + 10); for(ll i = 0; i < M; i++) { ll l, r, p; cin >> l >> r >> p; l--; rp[l].emplace_back(r, p); } V<PLL> dp(N + 2, PLL(0, -A)); dp[0].second = 0; for(ll i = 0; i < N; i++) { chmax(dp[i + 1].first, dp[i].first, dp[i].second); chmax(dp[i + 1].second, dp[i].first - (i + 1 == N ? 0 : A), dp[i].second - (i + 1 == N ? 0 : A)); for(auto P : rp[i]) { ll r, p; tie(r, p) = P; ll nxt_p0 = dp[i].first + p - (r == N ? 0 : A) - (i == 0 ? 0 : A); ll nxt_p1 = dp[i].second + p - (r == N ? 0 : A); chmax(dp[r].second, nxt_p0, nxt_p1); } } DEBUG(dp); cout << max(dp[N].first, dp[N].second) << endl; return 0; }