fork download
copy 
  1. /*
  2. ==> Don't stop when you're tired, stop when you're done.
  3. ==> Don't forget from the river to the sea palestine will be free 
  4. --> @author: MIDORIYA_
  5. */
  6. //*==============================================================
  7. #include <bits/stdc++.h>
  8. using namespace std;
  9. typedef long long ll;
  10. typedef double db;
  11. typedef long double ld;
  12. typedef pair<int, int> pii;
  13. typedef pair<ll, ll> pll;
  14. typedef vector<int> vi;
  15. typedef vector<ll> vll;
  16. typedef vector<db> vd;
  17. typedef vector<ld> vld;
  18. typedef vector<bool> vb;
  19. typedef vector<vector<ll>> vvl;
  20. typedef vector<vector<int>> vvi;
  21. typedef vector<pii> vii;
  22. typedef set<int> si;
  23. typedef set<ll> sl;
  24. #define pb push_back
  25. #define all(x) x.begin(), x.end()
  26. #define rall(x) x.rbegin(), x.rend()
  27. #define endl "\n"
  28. const ll MOD = 998244353, mod = 1e9 + 7, maxA = 1e5 + 5;
  29. #define time cerr << "Time Taken: " << (float)clock() / CLOCKS_PER_SEC << " Secs" << endl;
  30. //*===================>>>Fast-IO-Functions<<<=================
  31. void fastIO()
  32. {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(nullptr);
  35.     cout.tie(nullptr);
  36. }
  37. //*===================>>>File-IO-Functions<<<=================
  38. void fileIO()
  39. {
  40. #ifndef ONLINE_JUDGE
  41.     freopen("in.txt", "r", stdin);
  42.     freopen("out.txt", "w", stdout);
  43. #endif
  44. }
  45. //*===================>>>ONE-FOR-ALL-Function<<<==============
  46. void OneForAll()
  47. {
  48.     ll n;
  49.     cin >> n;
  50.     vector<ll> a(n);
  51.     for (ll &i : a)
  52.         cin >> i;
  53.     vector<ll> pref(n), suf(n), prv(n, -1), nxt(n, n + 1);
  54.     for (ll i = 0; i < n; i++)
  55.     {
  56.         if (i)
  57.             pref[i] = pref[i - 1];
  58.         pref[i] = max(pref[i], a[i]);
  59.     }
  60.     for (ll i = n - 1; i >= 0; i--)
  61.     {
  62.         if (i + 1 < n)
  63.             suf[i] = suf[i + 1];
  64.         suf[i] = max(suf[i], a[i]);
  65.     }
  66.     stack<pair<ll, ll>> st;
  67.     for (ll i = 0; i < n; i++)
  68.     {
  69.         while (st.size() and st.top().first < a[i])
  70.             st.pop();
  71.         if (st.size())
  72.             prv[i] = st.top().second;
  73.         st.push({a[i], i});
  74.     }
  75.     while (st.size())
  76.         st.pop();
  77.     for (ll i = n - 1; i >= 0; i--)
  78.     {
  79.         while (st.size() and st.top().first < a[i])
  80.             st.pop();
  81.         if (st.size())
  82.             nxt[i] = st.top().second;
  83.         st.push({a[i], i});
  84.     }
  85.     ll res = LLONG_MAX;
  86.     for (ll i = 1; i + 1 < n; i++)
  87.     {
  88.         ll p = max(0LL, prv[i]), p2 = min(n - 1, nxt[i]);
  89.         res = min(res, a[i] + pref[p] + suf[p2]);
  90.     }
  91.     cout << res;
  92. }
  93. int main()
  94. {
  95.     fastIO();
  96.     fileIO();
  97.     ll tc = 1;
  98.     // cin >> tc;
  99.     while (tc--)
  100.     {
  101.         OneForAll();
  102.     }
  103.     time;
  104.     return 0;
  105. }
Success #stdin #stdout #stderr 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9223372036854775807
stderr
copy 
Time Taken: 0.005801 Secs
https://ideone.com/oZn2dR
language:
C++14 (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!