fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. //#define ll long long
  6. #define ll int
  7. #define fi first
  8. #define se second
  9. #define MOD 1000000007
  10. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  11. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  12. #define ALL(x) (x).begin(),(x).end()
  13. #define ii pair<int,int>
  14. #define iii pair<int,pair<int,int>>
  15. //const int MOD = 998244853;
  16. const int MAXN = 1e6 + 7;
  17. int h[MAXN],n,m,l[MAXN],r[MAXN];
  18. struct Data{
  19.     ll s,x,y,u,v;
  20. };
  21. Data calc(){
  22.     vector<ii> q;
  23.     FOR(i,1,m){
  24.         while(q.size() && q.back().fi >= h[i])q.pop_back();
  25.         l[i] = (q.empty() ? 1 : q.back().se + 1);
  26.         q.push_back({h[i],i});
  27.     }
  28.     q.clear();
  29.     FOD(i,1,m){
  30.         while(q.size() && q.back().fi >= h[i])q.pop_back();
  31.         r[i] = (q.empty() ? m : q.back().se - 1);
  32.         q.push_back({h[i],i});
  33.     }
  34.     Data ans = {(ll)-1e9,0,0,0,0};
  35.     FOR(i,1,m){
  36.         ll S = (r[i] - l[i] + 1) * h[i];
  37.         if (ans.s < S)ans = {S,1,l[i],h[i],r[i]};
  38.     }
  39.     return ans;
  40. }
  41. int main(){
  42.     ios_base::sync_with_stdio(false);
  43.     cin.tie(0); cout.tie(0);
  44.     //freopen("MAXRECT.inp","r",stdin);
  45.     //freopen("MAXRECT.out","w",stdout);
  46.     cin >> n >> m;
  47.     FOR(i,1,m)cin >> h[i];
  48.     Data ans = calc();
  49.     FOR(i,1,m)h[i] = n - h[i];
  50.    // Data f = calc();
  51.     //if (ans.s < f.s)ans = {f.s,n - f.u + 1,f.y,n,f.v};
  52.     cout << ans.s << '\n' << ans.x << ' ' << ans.y << '\n' << ans.u << ' ' << ans.v;
  53.     return 0^0;
  54. }
Success #stdin #stdout 0.01s 7612KB
comments (?)
stdin
copy 
5 9
1 3 4 4 5 4 4 3 1
stdout
copy 
21
1 2
3 8
https://ideone.com/cjlwJs
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!