結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2020-06-26 22:17:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 440 ms / 2,000 ms |
コード長 | 1,123 bytes |
コンパイル時間 | 1,689 ms |
コンパイル使用メモリ | 176,132 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-07-04 21:58:30 |
合計ジャッジ時間 | 6,540 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;int main(){int N;cin >> N;vector<int> A(N);set<int> sl, sr;for(int i = 0; i < N; i++) {cin >> A[i];sr.insert(A[i]);}vector<int> ml(N), mr(N), Ml(N), Mr(N);ml[0] = A[0];mr[N - 1] = A[N - 1];Ml[0] = A[0];Mr[N - 1] = A[N - 1];for(int i = 1; i < N; i++){if(ml[i - 1] > A[i]) ml[i] = A[i];else ml[i] = ml[i - 1];}for(int i = 1; i < N; i++){if(mr[N - i] > A[N - 1 - i]) mr[N - 1 - i] = A[N - 1 - i];else mr[N - i - 1] = mr[N - i];}int ans = 1e9;sl.insert(A[0]);sr.erase(A[0]);for(int i = 1; i < N - 1; i++){sr.erase(A[i]);if(ml[i - 1] < A[i] && A[i] > mr[i + 1]) ans = min(ans, ml[i - 1] + A[i] + mr[i + 1]);auto ite = sl.lower_bound(A[i]), ite2 = sr.lower_bound(A[i]);if(ite != sl.end() && ite2 != sr.end()) ans = min(ans, A[i] + *ite + *ite2);sl.insert(A[i]);}int INF = 1e9;if(ans == INF){cout << -1 << endl;return 0;}cout << ans << endl;}