Advertisement
Guest User

Untitled

a guest
Sep 15th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.88 KB | None | 0 0
  1. // Comentário Noic OBI 2019 - Fase 2 - Programação Nível 2
  2. // Matriz Super Legal
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. typedef pair<int, int> pii;
  9.  
  10. const int maxn = 1e3+10;
  11.  
  12. int n, m;
  13.  
  14. // altura de cada célula
  15. int h[maxn][maxn];
  16.  
  17. // matrizes
  18. int A[maxn][maxn], B[maxn][maxn];
  19.  
  20. int j_0[maxn][maxn], j_1[maxn][maxn];
  21.  
  22. void calc_h(void)
  23. {
  24. for (int i = 1; i < n; i++)
  25. {
  26. for (int j = 1; j < m; j++)
  27. {
  28. if (!B[i][j]) continue;
  29.  
  30. // calculamos h[i][j] baseando-nos na célula acima
  31. if (B[i-1][j] == 1) h[i][j] = 1+h[i-1][j];
  32. else h[i][j] = 1;
  33. }
  34. }
  35. }
  36.  
  37. void calc_j0(void)
  38. {
  39. for (int i = 1; i < n; i++)
  40. {
  41. stack<pii> stk;
  42.  
  43. for (int j = 1; j < m; j++)
  44. {
  45. // algoritmo 2
  46.  
  47. while (!stk.empty() && stk.top().second >= h[i][j])
  48. stk.pop();
  49.  
  50. // se j0 não existe, digamos que ele será uma posição a
  51. // menos do limite (1)
  52. if (stk.empty()) j_0[i][j] = 0;
  53. else j_0[i][j] = stk.top().first;
  54.  
  55. stk.push({j, h[i][j]});
  56. }
  57. }
  58. }
  59.  
  60. void calc_j1(void)
  61. {
  62. for (int i = 1; i < n; i++)
  63. {
  64. stack<pii> stk;
  65.  
  66. for (int j = m-1; j >= 1; j--)
  67. {
  68. // algoritmo 2
  69.  
  70. while (!stk.empty() && stk.top().second >= h[i][j])
  71. stk.pop();
  72.  
  73. // se j1 não existe, digamos que ele será uma posição a
  74. // mais do que o limite (m-1)
  75. if (stk.empty()) j_1[i][j] = m;
  76. else j_1[i][j] = stk.top().first;
  77.  
  78. stk.push({j, h[i][j]});
  79. }
  80. }
  81. }
  82.  
  83. int main(void)
  84. {
  85. scanf("%d %d", &n, &m);
  86.  
  87. for (int i = 1; i <= n; i++)
  88. for (int j = 1; j <= m; j++)
  89. scanf("%d", &A[i][j]);
  90.  
  91. // checando todas as matrizes 2x2
  92. for (int i = 1; i < n; i++)
  93. for (int j = 1; j < m; j++)
  94. if (A[i][j]+A[i+1][j+1] <= A[i+1][j]+A[i][j+1])
  95. B[i][j] = 1;
  96.  
  97. calc_h();
  98.  
  99. calc_j0();
  100. calc_j1();
  101.  
  102. // resposta do problema
  103. int ans = 0;
  104.  
  105. for (int i = 1; i < n; i++)
  106. for (int j = 1; j < m; j++)
  107. if (h[i][j])
  108. ans = max(ans, (j_1[i][j]-j_0[i][j])*(h[i][j]+1)); // (x_m+1)*(y_m+1)
  109.  
  110. printf("%d\n", ans);
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement