fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N = 1e6 + 5;
  5.  
  6. int m, n;
  7. int a[N], L[N], R[N];
  8. int maxf = 0;
  9. int tlx, tly, brx, bry;
  10.  
  11. void solve(){
  12. 	stack<int> s;
  13. 	for (int i = 1; i <= n; i++){
  14.     	while (!s.empty() && a[i] <= a[s.top()]) s.pop();
  15.  
  16. 	    if (s.empty()) L[i] = 1;
  17. 	    else L[i] = s.top() + 1;
  18. 	    s.push(i);
  19. 	}
  20.   	while (s.size()) s.pop();
  21.  
  22.   	for (int i = n; i >= 1; i--){
  23.     	while (!s.empty() && a[i] <= a[s.top()]) s.pop();
  24.  
  25. 	    if (s.empty()) R[i] = n;
  26. 	    else R[i] = s.top() - 1;
  27. 	    s.push(i);
  28. 	}
  29.   	while (s.size()) s.pop();
  30.  
  31. }
  32. signed main(){
  33. 	cin.tie(0)->sync_with_stdio(0);
  34. 	freopen("maxrect.inp", "r", stdin);
  35.   	freopen("maxrect.out", "w", stdout);
  36.  
  37.   	cin >> m >> n;
  38.   	for (int i = 1; i <= n; i++){
  39.   		cin >> a[i];
  40.   	}
  41. 	solve();
  42.   	for (int i = 1; i <= n; i++){
  43.   		//cout << i << " " << L[i] << " " << R[i] << "\n";
  44.   		int tmp = a[i]*(R[i] - L[i] + 1);
  45.     	if (tmp > maxf){
  46. 	     	maxf = tmp;
  47. 	      	tlx = 1;
  48. 	      	tly = L[i];
  49. 	      	brx = a[i];
  50. 	      	bry = R[i];
  51. 	    }
  52.   	}
  53. 	for (int i = 1; i <= n; i++){
  54. 		a[i] = m - a[i];
  55. 	}
  56. 	solve();
  57.   	for (int i = 1; i <= n; i++){
  58.     	int tmp = a[i]*(R[i] - L[i] + 1);
  59.     	if (tmp > maxf){
  60. 	     	maxf = tmp;
  61. 		    tlx = m - a[i] + 1;
  62. 		    tly = L[i];
  63. 		    brx = m;
  64. 		    bry = R[i];	
  65. 	    }
  66.   	}
  67. 	cout << maxf << "\n";
  68. 	cout << tlx << " " << tly << "\n";
  69. 	cout << brx << " " << bry << "\n";
  70. }
Success #stdin #stdout 0.01s 5344KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AjnTxC
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!