Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2019
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. #include <fstream>
  2. #include <queue>
  3. #define Max 2005
  4. using namespace std;
  5. ifstream fin("meteoriti.in");
  6. ofstream fout("meteoriti.out");
  7. int N, M, R, matrice[Max][Max], x, maxim, arie_max, nr_arie, nr;
  8. int di[4] = {1, -1, 0, 0};
  9. int dj[4] = {0, 0, 1, -1};
  10. queue < pair < int, int > > C;
  11. struct coord
  12. {
  13. int r, c;
  14. } a, b;
  15. bool ok(int i, int j)
  16. {
  17. if(i < 1 || j < 1 || i > N || j > M)
  18. return false;
  19. if(matrice[i][j] != maxim)
  20. return false;
  21. return true;
  22. }
  23. void Fill(int x, int y)
  24. {
  25. int i, j, urmatorul_i, urmatorul_j;
  26. C.push(make_pair(x, y));
  27. while(!C.empty())
  28. {
  29. i = C.front().first;
  30. j = C.front().second;
  31. C.pop();
  32. nr_arie++;
  33. matrice[i][j] = -1;
  34. for(int d = 0; d < 4; d++)
  35. {
  36. urmatorul_i = i + di[d];
  37. urmatorul_j = j + dj[d];
  38. if(ok(urmatorul_i, urmatorul_j))
  39. C.push(make_pair(urmatorul_i, urmatorul_j));
  40. }
  41. }
  42. }
  43. void aduna(int x1, int y1, int x2, int y2, int v)
  44. {
  45. matrice[x1][y1] += v;
  46. matrice[x1][y2 + 1] -= v;
  47. matrice[x2 + 1][y1] -= v;
  48. matrice[x2 + 1][y2 + 1] += v;
  49. }
  50. void citire()
  51. {
  52. fin >> N >> M >> R;
  53. for(int i = 1; i <= R; ++i)
  54. {
  55. fin >> a.r >> a.c >> b.r >> b.c >> x;
  56. aduna(a.r, a.c, b.r, b.c, x);
  57. }
  58. for(int i = 1; i <= N; ++i)
  59. for(int j = 1; j <= M; ++j)
  60. matrice[i][j] += matrice[i - 1][j] + matrice[i][j - 1] - matrice[i - 1][j - 1];
  61. }
  62. void Solve()
  63. {
  64. for(int i = 1; i <= N; ++i)
  65. for(int j = 1; j <= M; ++j)
  66. if(matrice[i][j] > maxim)
  67. maxim = matrice[i][j];
  68. for(int i = 1; i <= N; ++i)
  69. for(int j = 1; j <= M; ++j)
  70. {
  71. if(matrice[i][j] == 0)
  72. nr++;
  73. if(matrice[i][j] == maxim)
  74. {
  75. nr_arie = 0;
  76. Fill(i, j);
  77. if(nr_arie > arie_max)
  78. arie_max = nr_arie;
  79. }
  80. }
  81. }
  82. int main()
  83. {
  84. citire();
  85. Solve();
  86. fout << arie_max << " " << nr;
  87. return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement