結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー |
![]() |
提出日時 | 2022-10-14 23:05:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 103 ms / 2,000 ms |
コード長 | 1,356 bytes |
コンパイル時間 | 2,807 ms |
コンパイル使用メモリ | 203,552 KB |
最終ジャッジ日時 | 2025-02-08 04:47:10 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#define rep(i,n) for(int i=0;i<(int)(n);i++) #define ALL(v) v.begin(),v.end() typedef long long ll; #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int n,m; cin>>n>>m; vector<ll> H(n+1); rep(i,n) cin>>H[i+1]; vector<int> X(m),Y(m); rep(i,m) cin>>X[i]>>Y[i]; vector<vector<ll>> dp(n+1,vector<ll>(2,-1)); vector<vector<int>> G(n+1); rep(i,m) G[X[i]].push_back(Y[i]); dp[1][0]=0; for(int i=1;i<n;i++){ for(auto nx:G[i]){ if(H[i]<H[nx]){ if(dp[i][0]!=-1) dp[nx][1]=max(dp[nx][1],dp[i][0]+H[nx]-H[i]); } else{ if(dp[i][0]!=-1) dp[nx][0]=max(dp[nx][0],dp[i][0]); if(dp[i][1]!=-1) dp[nx][0]=max(dp[nx][0],dp[i][1]); } } } ll ma=-1; rep(j,2) ma=max(ma,dp[n][j]); cout<<ma<<endl; vector<vector<ll>> dp1(n+1,vector<ll>(2,-1)); vector<vector<int>> G1(n+1); rep(i,m) G1[Y[i]].push_back(X[i]); dp1[n][0]=0; for(int i=n;i>1;i--){ for(auto nx:G1[i]){ if(H[i]<H[nx]){ if(dp1[i][0]!=-1) dp1[nx][1]=max(dp1[nx][1],dp1[i][0]+H[nx]-H[i]); } else{ if(dp1[i][0]!=-1) dp1[nx][0]=max(dp1[nx][0],dp1[i][0]); if(dp1[i][1]!=-1) dp1[nx][0]=max(dp1[nx][0],dp1[i][1]); } } } ma=-1; rep(j,2) ma=max(ma,dp1[1][j]); cout<<ma<<endl; return 0; }