結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
![]() |
提出日時 | 2020-06-26 21:29:47 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 1,320 bytes |
コンパイル時間 | 713 ms |
コンパイル使用メモリ | 88,856 KB |
実行使用メモリ | 6,632 KB |
最終ジャッジ日時 | 2024-07-04 19:43:46 |
合計ジャッジ時間 | 2,550 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <map>#include <queue>#include <cmath>#include <string>#include <vector>#include <algorithm>#include <functional>using namespace std;#pragma warning (disable: 4996)long long solve(vector<int> vec) {long long minx = (1LL << 60), ret = (1LL << 60);for (int i = (int)vec.size() - 1; i >= 0; i--) {if (vec[i] > minx) ret = min(ret, 1LL * vec[i] + minx);minx = min(minx, 1LL * vec[i]);}return ret;}long long N, A[1 << 18];int main() {cin >> N;for (int i = 1; i <= N; i++) cin >> A[i];pair<long long, int> minx = make_pair(1LL << 60, -1);for (int i = 1; i <= N; i++) minx = min(minx, make_pair(A[i], i));// パターン 1long long cl = (1LL << 60), cr = (1LL << 60);for (int i = 1; i <= minx.second - 1; i++) cl = min(cl, A[i]);for (int i = minx.second + 1; i <= N; i++) cr = min(cr, A[i]);long long z1 = cl + cr + A[minx.second];// パターン 2vector<int> val;for (int i = minx.second + 1; i <= N; i++) val.push_back(A[i]);long long z2 = solve(val) + A[minx.second];// パターン 3vector<int> val2;for (int i = minx.second - 1; i >= 1; i--) val2.push_back(A[i]);long long z3 = solve(val2) + A[minx.second];if (min({ z1, z2, z3 }) >= (1LL << 60)) cout << "-1" << endl;else cout << min({ z1, z2, z3 }) << endl;return 0;}