結果
問題 |
No.1095 Smallest Kadomatsu Subsequence
|
ユーザー |
|
提出日時 | 2020-08-20 02:40:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 426 ms / 2,000 ms |
コード長 | 1,325 bytes |
コンパイル時間 | 956 ms |
コンパイル使用メモリ | 100,232 KB |
実行使用メモリ | 15,232 KB |
最終ジャッジ日時 | 2024-10-12 15:19:26 |
合計ジャッジ時間 | 6,619 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <iomanip> #include <cmath> #include <stdio.h> #include <queue> #include <deque> #include <cstdio> #include <set> #include <map> #include <bitset> #include <stack> #include <cctype> using namespace std; int a[200020]; int ml[200020], mr[200020]; int main() { int n; cin >> n; for (int i = 0; i < n; i++) { cin >> a[i]; } int nl = 1000000007, nr = 1000000007; set<int> stl, str; for (int i = 0; i < n; i++) { if (nl > a[i]) { nl = a[i]; } if (nr > a[n - i - 1]) { nr = a[n - i - 1]; } ml[i] = nl; mr[n - i - 1] = nr; if (i > 1) { str.insert(a[i]); } } stl.insert(a[0]); int ans = 1000000007; for (int i = 1; i < n - 1; i++) { bool bo = true, bo1 = true; if (a[i] <= ml[i - 1] || a[i] <= mr[i + 1]) { bo = false; } auto itr = stl.set::upper_bound(a[i]); auto itr1 = str.set::upper_bound(a[i]); if (itr == stl.end() || itr1 == str.end()) { bo1 = false; } if (bo) { if (ans > ml[i - 1] + a[i] + mr[i + 1]) { ans = ml[i - 1] + a[i] + mr[i + 1]; } } if (bo1) { if (ans > *itr + a[i] + *itr1) { ans = *itr + a[i] + *itr1; } } str.erase(a[i + 1]); stl.insert(a[i]); } if (ans == 1000000007) { cout << "-1" << endl; return 0; } cout << ans << endl; }