結果

問題 No.1095 Smallest Kadomatsu Subsequence
ユーザー SAAD AHMAD
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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 second
const 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 argument
void 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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0