結果
問題 | No.1095 Smallest Kadomatsu Subsequence |
ユーザー |
|
提出日時 | 2022-08-04 00:19:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 30 ms / 2,000 ms |
コード長 | 2,973 bytes |
コンパイル時間 | 1,618 ms |
コンパイル使用メモリ | 170,880 KB |
実行使用メモリ | 11,008 KB |
最終ジャッジ日時 | 2024-09-13 18:46:16 |
合計ジャッジ時間 | 4,168 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define fast_io ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)#define pb push_back#define int long long#define ll long long#define ld long double#define rep(i, n) for (ll i=0; i<n; i++)#define repi(i, n) for (ll i=1; i<=n; i++)#define repi1(i, n) for (ll i = n; i >=0; i--)#define mem(v, ha) memset(v, ha, sizeof(v))#define all(a) a.begin(), a.end()#define allr(a) a.rbegin(), a.rend()#define CLOCK cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";typedef vector<ll> vi;typedef vector<vector<int>> vvi;typedef vector<pair<ll, ll>> vpi;typedef vector<char> vc;#define no cout << "NO\n"#define yes cout << "YES\n"#define mp make_pair#define ff first#define ss secondconst ll MOD = 1e9 + 7;const ll mod = 998244353 ;const long double PI = 3.141592653589793238460;const int inf = (int)(1e9);template<typename T> istream& operator>>(istream& in, vector<T>& a) {for (auto &x : a) in >> x; return in;};template<typename T> ostream& operator<<(ostream& out, vector<T>& a) {for (auto &x : a) out << x << ' '; return out;};// auto sum=[&](int use, int y){return use+y;};// function <void(int)>dfs=[&](int u) //void is the return type, int is the argumentvoid solve(){int n;cin >> n;vi a(n);rep(i, n)cin >> a[i];vi dp1(n), dp2(n);int mini = a[0];dp1[0] = a[0];for (int i = 1; i < n; i++){dp1[i] = dp1[i - 1];if (a[i] < mini){mini = a[i];dp1[i] = mini;}}dp2[n - 1] = a[n - 1];mini = a[n - 1];for (int i = n - 2; i >= 0; i--){ dp2[i] = dp2[i + 1];if (a[i] < mini){mini = a[i];dp2[i] = mini;}}//for (auto l : dp1)// cout << l << " ";int ans = INT_MAX;for (int i = 1; i < n - 1; i++){int ml = dp1[i - 1];int ma = dp2[i + 1];if (a[i] > ml && a[i] > ma){ans = min(ans, a[i] + ml + ma);}}vi dp3(n), dp4(n);int maxi = a[0];dp3[0] = a[0];for (int i = 1; i < n; i++){dp3[i] = dp3[i - 1];if (a[i] < maxi){maxi = a[i];dp3[i] = maxi;}}dp4[n - 1] = a[n - 1];maxi = a[n - 1];for (int i = n - 2; i >= 0; i--){ dp4[i] = dp4[i + 1];if (a[i] < maxi){maxi = a[i];dp4[i] = maxi;}}for (int i = 1; i < n - 1; i++){int ml = dp3[i - 1];int ma = dp4[i + 1];if (a[i] < ml && a[i] < ma){ans = min(ans, a[i] + ml + ma);}}if (ans == INT_MAX){cout << -1 << '\n';return;}cout << ans << '\n';}int32_t main(){fast_io;int T = 1;// cin >> T;while (T--){solve();}}