結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー | siro53 |
提出日時 | 2020-06-26 21:57:34 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 409 ms / 2,000 ms |
コード長 | 3,471 bytes |
コンパイル時間 | 2,210 ms |
コンパイル使用メモリ | 212,988 KB |
実行使用メモリ | 19,932 KB |
最終ジャッジ日時 | 2023-09-18 04:25:50 |
合計ジャッジ時間 | 7,272 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 2 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,376 KB |
testcase_08 | AC | 2 ms
4,376 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 2 ms
4,376 KB |
testcase_12 | AC | 2 ms
4,376 KB |
testcase_13 | AC | 11 ms
4,376 KB |
testcase_14 | AC | 11 ms
4,380 KB |
testcase_15 | AC | 11 ms
4,380 KB |
testcase_16 | AC | 11 ms
4,380 KB |
testcase_17 | AC | 12 ms
4,380 KB |
testcase_18 | AC | 11 ms
4,380 KB |
testcase_19 | AC | 12 ms
4,376 KB |
testcase_20 | AC | 11 ms
4,380 KB |
testcase_21 | AC | 11 ms
4,376 KB |
testcase_22 | AC | 12 ms
4,376 KB |
testcase_23 | AC | 402 ms
19,676 KB |
testcase_24 | AC | 409 ms
19,596 KB |
testcase_25 | AC | 394 ms
19,676 KB |
testcase_26 | AC | 403 ms
19,608 KB |
testcase_27 | AC | 398 ms
19,932 KB |
testcase_28 | AC | 260 ms
19,604 KB |
testcase_29 | AC | 261 ms
19,740 KB |
testcase_30 | AC | 298 ms
19,748 KB |
testcase_31 | AC | 300 ms
19,596 KB |
testcase_32 | AC | 300 ms
19,740 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; template <class T> inline bool chmax(T &a, T b) { if(a < b) { a = b; return 1; } return 0; } template <class T> inline bool chmin(T &a, T b) { if(a > b) { a = b; return 1; } return 0; } void debug() { cerr << "\n"; } template <class T> void debug(const T &x) { cerr << x << "\n"; } template <class T, class... Args> void debug(const T &x, const Args &... args) { cerr << x << " "; debug(args...); } template <class T> void debugVector(const vector<T> &v) { for(const T &x : v) { cerr << x << " "; } cerr << "\n"; } using ll = long long; #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() const double EPS = 1e-7; const int INF = 1 << 30; const ll LLINF = 1LL << 60; const double PI = acos(-1); constexpr int MOD = 1000000007; const int dx[4] = {1, 0, -1, 0}; const int dy[4] = {0, 1, 0, -1}; //------------------------------------- template <typename Monoid> struct SegmentTree { using F = function<Monoid(Monoid, Monoid)>; private: int n; vector<Monoid> node; Monoid E; F f; public: SegmentTree(vector<Monoid> v, Monoid e, const F func) : f(func), E(e) { int sz = v.size(); n = 1; while(n < sz) { n *= 2; } node.resize(2 * n - 1, E); for(int i = 0; i < sz; i++) { node[i + n - 1] = v[i]; } for(int i = n - 2; i >= 0; i--) { node[i] = f(node[2 * i + 1], node[2 * i + 2]); } } void update(int i, Monoid val) { i += (n - 1); node[i] = val; while(i > 0) { i = (i - 1) / 2; node[i] = f(node[2 * i + 1], node[2 * i + 2]); } } Monoid query(int a, int b, int i = 0, int l = 0, int r = -1) { if(r < 0) { r = n; } if(r <= a || b <= l) { return E; } if(a <= l && r <= b) { return node[i]; } Monoid vl = query(a, b, 2 * i + 1, l, (l + r) / 2); Monoid vr = query(a, b, 2 * i + 2, (l + r) / 2, r); return f(vl, vr); } Monoid operator[](const int &i) const { return node[i + n - 1]; } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vector<ll> a(n); for(auto &it : a) { cin >> it; } SegmentTree<ll> segmin(a, LLINF, [](ll x, ll y) { return min(x, y); }); ll ans = LLINF; // min max minを探す for(int i = 0; i < n; i++) { ll l = segmin.query(0, i); ll r = segmin.query(i + 1, n); if(l < a[i] && r < a[i]) { chmin(ans, l + a[i] + r); } } // 大小大 vector<ll> memo = a; // 今見てる要素より左にあって、今見てる要素よりも大きいa[i]の集合 set<ll> se; for(int i = 0; i < n; i++) { auto it = se.lower_bound(a[i]); if(it != se.end()) { memo[i] += *it; } else { memo[i] += LLINF; } se.insert(a[i]); } se.clear(); for(int i = n - 1; i >= 0; i--) { auto it = se.lower_bound(a[i]); if(it != se.end()) { memo[i] += *it; } else { memo[i] += LLINF; } se.insert(a[i]); } // debugVector(memo); chmin(ans, *min_element(ALL(memo))); cout << (ans >= LLINF ? -1 : ans) << endl; }