結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2021-05-31 15:20:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 342 ms / 2,000 ms |
コード長 | 1,003 bytes |
コンパイル時間 | 2,914 ms |
コンパイル使用メモリ | 173,784 KB |
実行使用メモリ | 25,984 KB |
最終ジャッジ日時 | 2024-11-08 21:17:46 |
合計ジャッジ時間 | 6,017 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define ll long long#define rep(i, n) for (int i = 0; i < (n); i++)#define P pair<int, int>const int INF = 1001001001;int main() {int n;cin >> n;vector<int> a(n);rep(i,n) cin >> a[i];vector<int> mxl(n), mxr(n), mnl(n, INF), mnr(n, INF);set<int> sl, sr;for (int i = 1; i < n; i++) {mnl[i] = min(mnl[i-1], a[i-1]);sl.insert(a[i-1]);auto it = sl.upper_bound(a[i]);if (it == sl.end()) mxl[i] = INF;else mxl[i] = *it;}for (int i = n-2; i >= 0; i--) {mnr[i] = min(mnr[i+1], a[i+1]);sr.insert(a[i+1]);auto it = sr.upper_bound(a[i]);if (it == sr.end()) mxr[i] = INF;else mxr[i] = *it;}int ans = INF;for (int i = 1; i < n-1; i++) {if (a[i] > mnl[i] && a[i] > mnr[i]) {ans = min(ans, a[i]+mnl[i]+mnr[i]);}if (a[i] < mxl[i] && a[i] < mxr[i]) {ans = min(ans, a[i]+mxl[i]+mxr[i]);}}if (ans == INF) ans = -1;cout << ans << endl;}