結果
問題 |
No.1095 Smallest Kadomatsu Subsequence
|
ユーザー |
![]() |
提出日時 | 2020-06-26 23:36:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 27 ms / 2,000 ms |
コード長 | 1,039 bytes |
コンパイル時間 | 1,290 ms |
コンパイル使用メモリ | 118,700 KB |
最終ジャッジ日時 | 2025-01-11 12:17:31 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<iostream> #include<string> #include<algorithm> #include<vector> #include<iomanip> #include<math.h> #include<complex> #include<queue> #include<deque> #include<stack> #include<map> #include<set> #include<bitset> #include<functional> #include<assert.h> #include<numeric> using namespace std; #define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) REP(i,0,n) using ll = long long; constexpr int inf=1e9+7; constexpr ll longinf=1LL<<60 ; constexpr ll mod=1e9+7 ; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n; cin>>n; vector<int> a(n+2); rep(i,n)cin>>a[i+1]; vector<int> l(n+2,inf), r(n+2,inf); rep(i,n)l[i+1]=r[i+1]=a[i+1]; rep(i,n+1)l[i+1]=min(l[i+1],l[i]); rep(i,n+1)r[n-i]=min(r[n-i],r[n-i+1]); int ans=inf; rep(i,n){ if(l[i]<a[i+1]&&a[i+1]>r[i+2])ans=min(ans,l[i]+a[i+1]+r[i+2]); if(l[i]>a[i+1]&&a[i+1]<r[i+2])ans=min(ans,l[i]+a[i+1]+r[i+2]); } if(ans==inf)cout<<-1<<endl; else cout<<ans<<endl; return 0; }