結果
問題 |
No.1095 Smallest Kadomatsu Subsequence
|
ユーザー |
![]() |
提出日時 | 2020-06-26 21:36:01 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 370 ms / 2,000 ms |
コード長 | 1,211 bytes |
コンパイル時間 | 1,850 ms |
コンパイル使用メモリ | 175,580 KB |
実行使用メモリ | 17,408 KB |
最終ジャッジ日時 | 2024-07-04 19:56:33 |
合計ジャッジ時間 | 6,068 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define int long long #define REP(i,m,n) for(int i=(m);i<(n);i++) #define rep(i,n) REP(i,0,n) #define pb push_back #define all(a) a.begin(),a.end() #define rall(c) (c).rbegin(),(c).rend() #define mp make_pair #define double long double #define endl '\n' typedef long long ll; typedef pair<ll,ll> pll; const ll inf=1e9+7; const ll mod=1e9+7; signed main(){ ll n;cin>>n; vector<ll>a(n); rep(i,n)cin>>a[i]; ll mi=inf; vector<ll>b(n,inf); vector<ll>c(n,inf); b[0]=a[0]; REP(i,1,n){ b[i]=min(b[i-1],a[i]); } c[n-1]=a[n-1]; for(int i=n-2;i>=0;i--){ c[i]=min(c[i+1],a[i]); } REP(i,1,n-1){ if(a[i]>b[i-1]&&a[i]>c[i+1]){ mi=min(mi,a[i]+b[i-1]+c[i+1]); } } set<ll>s,t; rep(i,n){ t.insert(a[i]); } t.erase(a[0]); t.erase(a[1]); s.insert(a[0]); REP(i,1,n-1){ auto itr1=s.upper_bound(a[i]); auto itr2=t.upper_bound(a[i]); if(itr1!=s.end()&&itr2!=t.end()){ mi=min(a[i]+*itr1+*itr2,mi); } s.insert(a[i]); t.erase(a[i+1]); } if(mi==inf)cout<<-1<<endl; else cout<<mi<<endl; }