結果
問題 | No.2100 [Cherry Alpha C] Two-way Steps |
ユーザー | Nzt3 |
提出日時 | 2022-12-23 13:48:01 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,112 bytes |
コンパイル時間 | 2,634 ms |
コンパイル使用メモリ | 207,520 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-11-18 03:59:36 |
合計ジャッジ時間 | 6,353 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 48 |
ソースコード
#include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int N,M; cin>>N>>M; vector<int>H(N); for(int &i:H)cin>>i; vector<vector<int>>G(N); for(int i=0;i<M;i++){ int x,y; cin>>x>>y; --x,--y; G[x].push_back(y), G[y].push_back(x); } vector<long long>cost(N*2,(long long)-1e18); cost[0]=0,cost[N]=0; for(int i=0;i<N;i++){ for(int j:G[i]){ if(j<i)continue; if(H[j]>H[i]){ cost[j+N]=max(cost[j+N],cost[i]+H[j]-H[i]); }else{ cost[j]=max(cost[j],cost[i]); cost[j]=max(cost[j],cost[i+N]); } } } cout<<(max(cost[N-1],cost[N*2-1])<0?-1ll:max(cost[N-1],cost[N*2-1]))<<'\n'; fill(cost.begin(),cost.end(),(long long)-1e18); cost[N-1]=cost[N*2-1]=0; for(int i=N-1;i>=0;i--){ for(int j:G[i]){ if(j>i)continue; if(H[j]>H[i]){ cost[j+N]=max(cost[j+N],cost[i]+H[j]-H[i]); }else{ cost[j]=max(cost[j],cost[i]); cost[j]=max(cost[j],cost[i+N]); } } } cout<<(max(cost[0],cost[N])<0?-1ll:max(cost[0],cost[N]))<<'\n'; }