fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5. typedef vector<int> vi;
  6. typedef vector<string> vs;
  7. typedef pair<int, int> pi;
  8. #define F first
  9. #define S second
  10. #define pb push_back
  11. #define mp make_pair
  12. #define sz(a) a.size()
  13. #define Print(a) for(int i = 0; i < a.size(); i++) {cout << a[i] << " ";} cout << endl;
  14. #define all(x) (x).begin(), (x).end()
  15. #define rall(x) (x).rbegin(), (x).rend()
  16. #define endl "\n"
  17. #define YES cout << "YES\n";
  18. #define NO cout << "NO\n";
  19.  
  20. void solve() {
  21.     int n; cin >> n;
  22.     vector<int> p(n);
  23.     for (int i = 0; i < n; ++i) {
  24.         cin >> p[i];
  25.     }
  26.  
  27.     vector<int> left(n, -1);
  28.     vector<int> right(n, n);
  29.  
  30.     stack<int> st;
  31.  
  32.     for (int i = 0; i < n; ++i) {
  33.         while (!st.empty() && p[st.top()] <= p[i]) {
  34.             st.pop();
  35.         }
  36.         if (!st.empty()) {
  37.             left[i] = st.top();
  38.         }
  39.         st.push(i);
  40.     }
  41.  
  42.     while (!st.empty()) st.pop();
  43.  
  44.     for (int i = n - 1; i >= 0; --i) {
  45.         while (!st.empty() && p[st.top()] < p[i]) {
  46.             st.pop();
  47.         }
  48.         if (!st.empty()) {
  49.             right[i] = st.top();
  50.         }
  51.         st.push(i);
  52.     }
  53.  
  54.     long long total = 0;
  55.     for (int i = 0; i < n; ++i) {
  56.         long long count = (long long)(i - left[i]) * (right[i] - i);
  57.         total += (long long)p[i] * count;
  58.     }
  59.  
  60.     long long num_subarrays = (long long)n * (n + 1) / 2;
  61.     double expected_value = (double)total / num_subarrays;
  62.  
  63.     cout << fixed << setprecision(10) << expected_value << endl;
  64. }
  65.  
  66. int32_t main() {
  67.     ios_base::sync_with_stdio(false);
  68.     cin.tie(0);
  69.     freopen("random.in", "r", stdin);
  70.     /*
  71.     freopen("wtf.out", "w", stdout);
  72.     */
  73.     int t = 1;
  74.     //cin >> t;
  75.     while (t--) {
  76.         solve();
  77.     }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-nan
https://ideone.com/Wto0Qf
language:
C++ (gcc 8.3)
created:
1 day 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!