Advertisement
Guest User

Untitled

a guest
Feb 20th, 2020
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.60 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. ifstream fin("dreptunghi.in");
  5. ofstream fout("dreptunghi.out");
  6. const int nmax = 1000;
  7.  
  8. int n, m, a[nmax + 5], b[nmax + 5], st[nmax + 5], dr[nmax + 5],aux[nmax + 5][nmax + 5], ans;
  9. bool matrix[nmax + 5][nmax + 5];
  10. stack < int > S;
  11.  
  12. void read()
  13. {
  14. fin >> n >> m;
  15. for(int i = 1; i <= n; ++i)
  16. for(int j = 1; j <= m; ++j)
  17. fin >> matrix[i][j];
  18. }
  19.  
  20.  
  21. int Arie(int *v)
  22. {
  23. while(!S.empty())
  24. S.pop();
  25. S.push(0);
  26. for(int i = 1; i <= m; ++i)
  27. {
  28. while(!S.empty() && v[i] <= v[S.top()])
  29. S.pop();
  30. if(S.empty())
  31. st[i] = 1;
  32. else
  33. st[i] = S.top() + 1;
  34. S.push(i);
  35. }
  36. while(!S.empty())
  37. S.pop();
  38. S.push(m + 1);
  39. for(int i = m; i >= 1; i--)
  40. {
  41. while(!S.empty() && v[i] <= v[S.top()])
  42. S.pop();
  43. if(S.empty())
  44. dr[i] = m;
  45. else
  46. dr[i] = S.top() - 1;
  47. S.push(i);
  48. }
  49. int maxx = 0;
  50. for(int i = 1; i < n; ++i)
  51. maxx = max(maxx, (dr[i] - st[i] + 1)*v[i]);
  52. return maxx;
  53. }
  54. void solve()
  55. {
  56. for(int i = 1; i <= n; ++i)
  57. {
  58. for(int j = 1; j <= m; ++j)
  59. if(matrix[i][j] == 1)
  60. aux[i][j] = aux[i - 1][j] + 1;
  61. a[i] = max(a[i - 1], Arie(aux[i]));
  62. }
  63. for(int i = 1; i <= n; ++i)
  64. for(int j = 1; j <= m; ++j)
  65. aux[i][j] = 0;
  66. for(int i = 1; i <= n; ++i)
  67. ans = max(ans, a[i]);
  68. fout << ans;
  69. }
  70. int main()
  71. {
  72. read();
  73. solve();
  74. return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement