結果
問題 | 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);}