fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 2e5 + 5;
  5.  
  6. int a[N], l[N], r[N];
  7. int n;
  8. int ans, ansL, ansR;
  9.  
  10. int main()
  11. {
  12.     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  13.     //freopen("input.txt","r",stdin);
  14.     int nTest; cin >> nTest;
  15.     while (nTest--){
  16.         cin >> n;
  17.         for(int i=1; i<=n; i++) cin >> a[i];
  18.         for(int i=1; i<=n; i++){
  19.             l[i] = i;
  20.             while (l[i] > 1 && a[l[i] - 1] >= a[i]) l[i] = l[l[i] - 1];
  21.         }
  22.         for(int i=n; i>=1; i--){
  23.             r[i] = i;
  24.             while (r[i] < n && a[r[i] + 1] >= a[i]) r[i] = r[r[i] + 1];
  25.         }
  26.         ans = -1;
  27.         for(int i=1; i<=n; i++){
  28.             if ((r[i] - l[i] + 1) * a[i] > ans){
  29.                 ans = (r[i] - l[i] + 1) * a[i];
  30.                 ansL = l[i];
  31.                 ansR = r[i];
  32.             }
  33.         }
  34.         cout << ans << " " << ansL << " " << ansR << '\n';
  35.     }
  36.  
  37.     return 0;
  38. }
Success #stdin #stdout 0s 4708KB
comments (?)
stdin 
2
4
3 4 3 1
4
1 2 1 3
stdout 
9 1 3
4 1 4
https://ideone.com/bsCxZe
SPOJ - KAGAIN
language:
C++14 (gcc 8.3)
created:
4 years 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!