結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2022-09-25 17:05:50 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,788 ms / 2,000 ms |
コード長 | 1,803 bytes |
コンパイル時間 | 1,483 ms |
コンパイル使用メモリ | 143,180 KB |
実行使用メモリ | 9,504 KB |
最終ジャッジ日時 | 2024-12-22 13:05:25 |
合計ジャッジ時間 | 21,306 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <cassert>#include <cmath>#include <climits>#include <algorithm>#include <iostream>#include <iomanip>#include <climits>#include <map>#include <queue>#include <set>#include <cstring>#include <vector>using namespace std;typedef long long ll;int main() {int N;cin >> N;vector<int> A(N);for (int i = 0; i < N; ++i) {cin >> A[i];}vector<int> L(N);vector<int> LA;vector<int> LL(N, -1);vector<int> R(N);vector<int> RA;vector<int> RR(N, -1);int min_v = INT_MAX;for (int i = 0; i <= N - 1; ++i) {int a = A[i];auto it = lower_bound(LA.begin(), LA.end(), a);int idx = it - LA.begin();if (it != LA.end()) {LL[i] = a + LA[idx];}LA.insert(LA.begin() + idx, a);min_v = min(min_v, a);L[i] = min_v;}min_v = INT_MAX;for (int i = N - 1; i >= 0; --i) {int a = A[i];auto it = lower_bound(RA.begin(), RA.end(), a);int idx = it - RA.begin();if (it != RA.end()) {RR[i] = a + RA[idx];}RA.insert(RA.begin() + idx, a);min_v = min(min_v, a);R[i] = min_v;}/*for (int i = 0; i < N; ++i) {cerr << LL[i] << " ";}cerr << endl;for (int i = 0; i < N; ++i) {cerr << RR[i] << " ";}cerr << endl;*/int ans = INT_MAX;for (int i = 1; i <= N - 2; ++i) {int a = A[i];int l = LL[i];int r = RR[i];if (l == -1) continue;if (r == -1) continue;int v = l + r - a;ans = min(ans, v);}for (int i = 1; i <= N - 2; ++i) {int a = A[i];int l = L[i - 1];int r = R[i + 1];if (l > a) continue;if (r > a) continue;int v = a + l + r;ans = min(ans, v);}if (ans == INT_MAX) {cout << -1 << endl;} else {cout << ans << endl;}return 0;}