結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2021-05-04 21:41:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 330 ms / 2,000 ms |
コード長 | 3,037 bytes |
コンパイル時間 | 3,711 ms |
コンパイル使用メモリ | 190,092 KB |
実行使用メモリ | 15,104 KB |
最終ジャッジ日時 | 2024-07-23 16:59:01 |
合計ジャッジ時間 | 7,658 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#pragma region#define _USE_MATH_DEFINES#include <iostream>#include <string>#include <algorithm>#include <cmath>#include <cstdlib>#include <vector>#include <map>#include <queue>#include <stack>#include <set>#include <list>#include <iomanip>#include <cstdint>#include <bitset>#include <sstream>#include <regex>#include <fstream>#include <array>#include <atcoder/all>using namespace atcoder;using mint = modint1000000007;//using mint = modint998244353;//using mint = modint;using namespace std;typedef long long ll;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using vvl = vector<vl>;using pint = pair<int, int>;using pll = pair<ll, ll>;using vpint = vector<pint>;using vvpint = vector<vpint>;using vmint = vector<mint>;using vvmint = vector<vmint>;//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()#pragma region GCDll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}#pragma endregion#pragma region LCMll lcm(ll a, ll b){return a / gcd(a, b) * b;}#pragma endregion#pragma region chmintemplate<class T> inline bool chmin(T& a, T b){if (a > b){a = b;return true;}return false;}#pragma endregion#pragma region chmaxtemplate<class T> inline bool chmax(T& a, T b){if (a < b){a = b;return true;}return false;}#pragma endregion#pragma region グリッド内チェックbool out(int x, int y, int h, int w){if (x < 0 || h <= x || y < 0 || w <= y)return true;else return false;}#pragma endregion#pragma region Dijkstravl dijkstra(vector<vector<pair<int, ll>>> v, int s){ll INF = 1e18;int MAX = 1e6;vl res(MAX, INF);priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;q.push({ 0,s });while (!q.empty()){int now;ll d;tie(d, now) = q.top();q.pop();if (!chmin(res[now], d))continue;for (auto p : v[now]){int next;ll c;tie(next, c) = p;if (res[next] <= res[now] + c)continue;q.push({ res[now] + c,next });}}return res;}#pragma endregion#pragma endregionint main(){int n; cin >> n;vi a(n); rep(i, n)cin >> a[i];vi lsmall(n), rsmall(n);lsmall[0] = a[0];rsmall[n - 1] = a[n - 1];for (int i = 1; i < n; ++i)lsmall[i] = min(lsmall[i - 1], a[i]);rrep(i, n - 1)rsmall[i] = min(rsmall[i + 1], a[i]);int res = 1e9;for (int i = 1; i < n - 1; ++i){if (a[i] > lsmall[i - 1] && a[i] > rsmall[i + 1]){chmin(res, a[i] + lsmall[i - 1] + rsmall[i + 1]);}}set<int> l, r;l.insert(a[0]);rep(i, n - 1)r.insert(a[i + 1]);for (int i = 1; i < n - 1; ++i){r.erase(a[i]);auto lit = l.lower_bound(a[i]);auto rit = r.lower_bound(a[i]);if (lit == l.end() || rit == r.end())continue;chmin(res, *lit + a[i] + *rit);l.insert(a[i]);}if (res == 1e9)cout << -1 << endl;else cout << res << endl;}