結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2020-08-19 19:39:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,355 bytes |
コンパイル時間 | 1,737 ms |
コンパイル使用メモリ | 176,660 KB |
実行使用メモリ | 823,296 KB |
最終ジャッジ日時 | 2024-10-12 05:15:08 |
合計ジャッジ時間 | 6,636 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 10 MLE * 1 -- * 19 |
ソースコード
#include <algorithm>#include <bits/stdc++.h>using namespace std;#define rep(i, n) for (int i = 0; i < (int)(n); i++)#define all(x) (x).begin(), (x).end()#define ll long long#define ld long double#define INF 1000000000000000000typedef pair<ll, ll> pll;int main() {cin.tie(0);ios::sync_with_stdio(false);int N;cin >> N;vector<ll> A(N);rep(i, N) { cin >> A[i]; }vector<ll> lmin(N), rmin(N);ll lmi = INF, rmi = INF;rep(i, N) {lmi = min(lmi, A[i]);lmin[i] = lmi;}for (int i = N - 1; i > -1; i--) {rmi = min(rmi, A[i]);rmin[i] = rmi;}vector<set<ll>> lse(N), rse(N);set<ll> sel, ser;sel.insert(INF), ser.insert(INF);rep(i, N) {sel.insert(A[i]);lse[i] = sel;}for (int i = N - 1; i > -1; i--) {ser.insert(A[i]);rse[i] = ser;}ll atype = INF, btype = INF;for (int i = 1; i < N - 1; i++) {if (A[i] > rmin[i + 1] && A[i] > lmin[i - 1])atype = min(atype, A[i] + rmin[i + 1] + lmin[i - 1]);}for (int i = 1; i < N - 1; i++) {ll a = *lse[i - 1].upper_bound(A[i]);ll b = *rse[i + 1].upper_bound(A[i]);btype = min(btype, a + A[i] + b);}ll ans = min(atype, btype);cout << (ans == INF ? -1 : ans) << endl;}