Advertisement
nicuvlad76

Untitled

Nov 5th, 2018
212
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream fin ("dreptunghi1.in");
  4. ofstream fout ("dreptunghi1.out");
  5. int n, m, z, v[10001], lin, col;
  6. bitset <10001> a[10001];
  7. long long x, ans = -1;
  8.  
  9. long long MaxArea()
  10. {
  11. stack <int> st;
  12. int i = 0;
  13. long long area = 0, maxi = -1;
  14. while (i < m)
  15. {
  16. if (st.empty() || v[st.top()] <= v[i])
  17. st.push(i++);
  18. else
  19. {
  20. int top = st.top();
  21. st.pop();
  22. area = v[top] * (st.empty() ? i : i - st.top() - 1);
  23. if (area > maxi)
  24. maxi = area;
  25. }
  26. }
  27. while (!st.empty())
  28. {
  29. int top = st.top();
  30. st.pop();
  31. area = v[top] * (st.empty() ? i : i - st.top() - 1);
  32. if (area > maxi)
  33. maxi = area;
  34. }
  35. return maxi;
  36. }
  37.  
  38. int main()
  39. {
  40. fin >> n >> m >> z;
  41. for (int i = 1; i <= z; i++)
  42. {
  43. fin >> lin >> col;
  44. a[lin][col] = 1;
  45. }
  46. for (int i = 1; i <= n; i++)
  47. {
  48. for (int j = 1; j <= m; j++)
  49. v[j - 1] = (a[i][j] == 0? v[j - 1] + 1 : 0);
  50. int x = MaxArea();
  51. if (x > ans)
  52. ans = x;
  53. }
  54. fout << ans;
  55. return 0;
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement