結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2021-04-15 03:09:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 1,383 bytes |
コンパイル時間 | 719 ms |
コンパイル使用メモリ | 76,396 KB |
実行使用メモリ | 8,704 KB |
最終ジャッジ日時 | 2024-07-01 01:38:08 |
合計ジャッジ時間 | 4,336 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>using namespace std;int main(){int n;cin >> n;vector<int> a(n);for(auto &p: a) cin >> p;vector<vector<int>> vec(5, vector<int>(n));for(int i = 0; i < 5; i++) vec[i][0] = a[0];for(int i = 0; i < 5; i++) vec[i][n-1] = a[n-1];for(int i = 1; i < n; i++){vec[0][i] = a[i];vec[1][i] = min(vec[1][i-1], a[i]);vec[2][i] = max(vec[2][i-1], a[i]);}for(int i = n-2; i >= 0; i--){vec[3][i] = min(vec[3][i+1], a[i]);vec[4][i] = max(vec[4][i+1], a[i]);}int ans = 1001001001;for(int i = 1; i < n-1; i++){for(int bit = 0; bit < (1 << 2); bit++){vector<int> coans;coans.push_back(vec[0][i]);if(bit & (1 << 0)) coans.push_back(vec[1][i-1]);else coans.push_back(vec[2][i-1]);if(bit & (1 << 1)) coans.push_back(vec[3][i+1]);else coans.push_back(vec[4][i+1]);if(coans[0] == min(coans[0], min(coans[1], coans[2]))|| coans[0] == max(coans[0], max(coans[1], coans[2]))){ans = min(ans, coans[0]+coans[1]+coans[2]);//cerr << coans[0] << " " << coans[1] << " " << coans[2] << endl;}}}if(ans == 1001001001) ans = -1;cout << ans << endl;return 0;}