Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <fstream>
- #include <queue>
- #define Max 2005
- using namespace std;
- ifstream fin("meteoriti.in");
- ofstream fout("meteoriti.out");
- int N, M, R, matrice[Max][Max], x, maxim, arie_max, nr_arie, nr;
- int di[4] = {1, -1, 0, 0};
- int dj[4] = {0, 0, 1, -1};
- queue < pair < int, int > > C;
- struct coord
- {
- int r, c;
- } a, b;
- bool ok(int i, int j)
- {
- if(i < 1 || j < 1 || i > N || j > M)
- return false;
- if(matrice[i][j] != maxim)
- return false;
- return true;
- }
- void Fill(int x, int y)
- {
- int i, j, urmatorul_i, urmatorul_j;
- C.push(make_pair(x, y));
- while(!C.empty())
- {
- i = C.front().first;
- j = C.front().second;
- C.pop();
- nr_arie++;
- matrice[i][j] = -1;
- for(int d = 0; d < 4; d++)
- {
- urmatorul_i = i + di[d];
- urmatorul_j = j + dj[d];
- if(ok(urmatorul_i, urmatorul_j))
- C.push(make_pair(urmatorul_i, urmatorul_j));
- }
- }
- }
- void aduna(int x1, int y1, int x2, int y2, int v)
- {
- matrice[x1][y1] += v;
- matrice[x1][y2 + 1] -= v;
- matrice[x2 + 1][y1] -= v;
- matrice[x2 + 1][y2 + 1] += v;
- }
- void citire()
- {
- fin >> N >> M >> R;
- for(int i = 1; i <= R; ++i)
- {
- fin >> a.r >> a.c >> b.r >> b.c >> x;
- aduna(a.r, a.c, b.r, b.c, x);
- }
- for(int i = 1; i <= N; ++i)
- for(int j = 1; j <= M; ++j)
- matrice[i][j] += matrice[i - 1][j] + matrice[i][j - 1] - matrice[i - 1][j - 1];
- }
- void Solve()
- {
- for(int i = 1; i <= N; ++i)
- for(int j = 1; j <= M; ++j)
- if(matrice[i][j] > maxim)
- maxim = matrice[i][j];
- for(int i = 1; i <= N; ++i)
- for(int j = 1; j <= M; ++j)
- {
- if(matrice[i][j] == 0)
- nr++;
- if(matrice[i][j] == maxim)
- {
- nr_arie = 0;
- Fill(i, j);
- if(nr_arie > arie_max)
- arie_max = nr_arie;
- }
- }
- }
- int main()
- {
- citire();
- Solve();
- fout << arie_max << " " << nr;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement