結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
![]() |
提出日時 | 2022-10-14 21:45:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 99 ms / 2,000 ms |
コード長 | 1,946 bytes |
コンパイル時間 | 1,346 ms |
コンパイル使用メモリ | 115,192 KB |
最終ジャッジ日時 | 2025-02-08 03:37:16 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <string> #include <tuple> #include <vector> #define mkp make_pair #define mkt make_tuple #define rep(i, n) for (int i = 0; i < (int)(n); ++i) #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; const ll MOD = 1e9 + 7; // const ll MOD = 998244353; template <class T> void chmin(T &a, const T &b) { if (a > b) a = b; } template <class T> void chmax(T &a, const T &b) { if (a < b) a = b; } const ll INF = 1e18; ll calc(vector<ll> H, vector<int> X, vector<int> Y) { const int N = H.size(); const int M = X.size(); vector<vector<int>> g(N); rep(i, M) g[X[i]].push_back(Y[i]); vector<vector<ll>> dp(N, vector<ll>(2, -INF)); dp[0][0] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < 2; j++) { const ll value = dp[i][j]; if (value == -INF) continue; for (auto to : g[i]) { if (j == 1 && H[i] < H[to]) continue; int nj = 0; if (H[i] < H[to]) nj = 1; chmax(dp[to][nj], value + max(0ll, H[to] - H[i])); } } } return max(dp[N - 1][0], dp[N - 1][1]); } void solve() { int N, M; cin >> N >> M; vector<ll> H(N); rep(i, N) cin >> H[i]; vector<int> X(M), Y(M); rep(i, M) { cin >> X[i] >> Y[i]; X[i]--; Y[i]--; } ll ans1 = calc(H, X, Y); reverse(all(H)); rep(i, M) { X[i] = N - 1 - X[i]; Y[i] = N - 1 - Y[i]; } swap(X, Y); ll ans2 = calc(H, X, Y); if (ans1 == -INF) cout << -1 << endl; else cout << ans1 << endl; if (ans2 == -INF) cout << -1 << endl; else cout << ans2 << endl; } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); solve(); return 0; }