結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
👑 ![]() |
提出日時 | 2020-10-04 11:46:02 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,003 bytes |
コンパイル時間 | 1,697 ms |
コンパイル使用メモリ | 172,624 KB |
実行使用メモリ | 10,752 KB |
最終ジャッジ日時 | 2024-07-19 07:34:15 |
合計ジャッジ時間 | 6,318 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 20 TLE * 1 -- * 9 |
ソースコード
#include<bits/stdc++.h>using namespace std;using LL = long long;using ULL = unsigned long long;#define rep(i,n) for(int i=0; i<(n); i++)int N;int A[200000];int X[200000][4];const int INF = 500000000;int main() {cin >> N;rep(i, N) cin >> A[i];rep(i, N) rep(j, N) X[i][j] = INF;for (int i = 0; i < N - 1; i++) X[i + 1][0] = min(X[i][0], A[i]);for (int i = N - 1; i >= 1; i--) X[i - 1][1] = min(X[i][1], A[i]);set<int> S; S.insert(INF);for (int i = 0; i < N - 1; i++) { S.insert(A[i]); X[i + 1][2] = *S.upper_bound(A[i + 1]); }S.clear(); S.insert(INF);for (int i = N - 1; i >= 1; i--) { S.insert(A[i]); X[i - 1][3] = *S.upper_bound(A[i - 1]); }int ans = INF;for (int i = 1; i < N - 1; i++) {if (X[i][0] < A[i] && A[i] > X[i][1]) ans = min(ans, X[i][0] + A[i] + X[i][1]);if (X[i][2] > A[i] && A[i] < X[i][3]) ans = min(ans, X[i][2] + A[i] + X[i][3]);}cout << (ans == INF ? -1 : ans) << endl;return 0;}