結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
![]() |
提出日時 | 2022-10-14 21:40:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 1,232 bytes |
コンパイル時間 | 4,197 ms |
コンパイル使用メモリ | 255,092 KB |
最終ジャッジ日時 | 2025-02-08 03:33:55 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include <stdio.h>#include <bits/stdc++.h>#include <atcoder/all>using namespace atcoder;using mint = modint998244353;using namespace std;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf32 1000000001#define Inf64 2000000000000000001void solve(vector<long long> h,vector<int> x,vector<int> y){int n = h.size();vector<vector<int>> E(n);rep(i,x.size()){E[min(x[i],y[i])].push_back(max(x[i],y[i]));}vector dp(n,vector<long long>(2,-Inf64));dp[0][0] = 0;dp[0][1] = 0;rep(i,n-1){rep(j,2){if(dp[i][j]==-Inf64)continue;rep(k,E[i].size()){int to = E[i][k];int F;if(h[i] < h[to])F = 1;else F = 0;if(F==j&&j==1)continue;long long C = 0;if(F==1)C = h[to] - h[i];dp[to][F] = max(dp[to][F],dp[i][j]+C);}}}/*rep(i,n){cout<<dp[i][0]<<','<<dp[i][1]<<endl;}*/long long ans = max(dp[n-1][0],dp[n-1][1]);if(ans==-Inf64)ans = -1;cout<<ans<<endl;}int main(){int n,m;cin>>n>>m;vector<long long> 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]--;}solve(h,x,y);rep(i,m){x[i] = n-1-x[i];y[i] = n-1-y[i];}reverse(h.begin(),h.end());solve(h,x,y);return 0;}