結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-08-28 04:07:01 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,216 ms / 2,000 ms |
コード長 | 1,423 bytes |
コンパイル時間 | 4,086 ms |
コンパイル使用メモリ | 216,824 KB |
最終ジャッジ日時 | 2025-01-13 15:55:12 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#pragma GCC optimize("O3") #include <bits/stdc++.h> using namespace std; using ll=long long; using P=pair<ll,ll>; template<class T> using V=vector<T>; #define fi first #define se second #define all(v) (v).begin(),(v).end() const ll inf=(1e18); //const ll mod=998244353; const ll mod=1000000007; ll GCD(ll a,ll b) {return b ? GCD(b,a%b):a;} ll LCM(ll c,ll d){return c/GCD(c,d)*d;} struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init; template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; } int main(){ int n; cin>>n; set<int> l,r; V<int> a(n); for(int i=0;i<n;i++){ cin>>a[i]; r.insert(a[i]); } int ans=INT_MAX; for(int i=0;i<n;i++){ r.erase(a[i]); if(l.size()&&r.size()){ if(*l.begin()<a[i]&&a[i]>*r.begin()){ chmin(ans,*l.begin()+*r.begin()+a[i]); } } l.insert(a[i]); } for(int i=0;i<n;i++){ r.insert(a[i]); } l.clear(); for(int i=0;i<n;i++){ r.erase(a[i]); if(l.size()&&r.size()){ auto itl=l.lower_bound(a[i]),itr=r.lower_bound(a[i]); if(itl!=l.end()&&itr!=r.end()){ chmin(ans,*itl+*itr+a[i]); } } l.insert(a[i]); } cout<<(ans>=INT_MAX?-1:ans)<<"\n"; }