結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2020-07-05 08:59:23 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 375 ms / 2,000 ms |
コード長 | 1,676 bytes |
コンパイル時間 | 988 ms |
コンパイル使用メモリ | 106,976 KB |
最終ジャッジ日時 | 2025-01-11 15:52:44 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <stdio.h> #include <string.h> #include <limits.h> #include <math.h> #include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> #include <set> #include <stack> #include <queue> typedef unsigned long long ULLONG; typedef long long LLONG; static const LLONG MOD_NUM = 1000000007;//998244353; template<class _T> static void getval(_T& a) { std::cin >> a; } template<class _T> static void getval(_T& a, _T& b) { std::cin >> a >> b; } template<class _T> static void getval(_T& a, _T& b, _T& c) { std::cin >> a >> b >> c; } static void exec(); int main() { exec(); fflush(stdout); return 0; } static void exec() { int N; getval(N); std::vector<LLONG> ai(N), minL(N + 1, MOD_NUM), minR(N + 1, MOD_NUM); LLONG minVal = MOD_NUM; std::set<LLONG> left, right; for (int i = 0; i < N; i++) { getval(ai[i]); minL[i + 1] = minL[i]; if (minVal > ai[i]) { minVal = ai[i]; minL[i + 1] = minVal; } right.insert(ai[i]); } minVal = MOD_NUM; for (int i = N - 1; i > 0; i--) { minR[i] = minR[i + 1]; if (minVal > ai[i]) { minVal = ai[i]; minR[i] = minVal; } } LLONG ans = MOD_NUM, pta = 0, ptb = 0; left.insert(ai[0]); right.erase(ai[0]); for (int i = 1; i < N - 1; i++) { if ((minL[i] < ai[i]) && (ai[i] > minR[i])) { pta = minL[i] + ai[i] + minR[i]; if (ans > pta) { ans = pta; } } right.erase(ai[i]); auto lm = left.lower_bound(ai[i]); auto rm = right.lower_bound(ai[i]); if (lm != left.end() && rm != right.end()) { ptb = *lm + ai[i] + *rm; if (ans > ptb) { ans = ptb; } } left.insert(ai[i]); } if (ans >= MOD_NUM) ans = -1; printf("%lld\n", ans); }