#504546 (C++14) No.1095 Smallest Kadomatsu Subsequence

• 問題: No.1095 Smallest Kadomatsu Subsequence
• ユーザー: Ahykw
• 提出日時: 2020-06-28 19:12:38
• 言語: C++14 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 378 ms / 2,000 ms
• コード長: 1,793 bytes
• コンパイル時間: 1,880 ms
• コンパイル使用メモリ: 182,312 KB
• 実行使用メモリ: 13,440 KB
• 最終ジャッジ日時: 2024-07-08 00:48:45
• 合計ジャッジ時間: 6,025 ms
• ジャッジサーバーID （参考情報）: judge5 / judge1

ファイルパターン	結果
sample	AC * 3
other	AC * 30

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif
void d_err() {
    cerr << endl;
}
template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}
template <typename T>
void print(T x) {
    cout << x << endl;
}
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REVFOR(i, m, n) for (int i = (n - 1); i >= (m); --i)
#define REP(i, n) FOR(i, 0, n)
#define REVREP(i, n) REVFOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;
ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i, N) cin >> A[i];
    multiset<int> l, r;
    REP(i, N) r.insert(A[i]);
    ll ans = INF;
    REP(i, N) {
        ll b = A[i];
        r.erase(b);
        if (!l.empty() && !r.empty()) {
            // large
            auto a = *l.begin();
            auto c = *r.begin();
            if (a < b && c < b) ans = min(ans, a + b + c);
            // small
            auto a_it = l.lower_bound(b);
            auto c_it = r.lower_bound(b);
            if (a_it != l.end() && c_it != r.end()) {
                ans = min(ans, *a_it + b + *c_it);
            }
        }
        l.insert(b);
    }
    if (ans == INF) print(-1);
    else print(ans);
    
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX