Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ii = pair<int, int>;
- #define ff first
- #define ss second
- #define pb push_back
- const int N = 1005;
- int psum[N][N][2];
- char mat[N][N];
- bool skip[N][N];
- int r, c;
- int l, h;
- int soma(int i, int j, int x, int y, int t){
- return psum[i][j][t] - psum[x-1][j][t] - psum[i][y-1][t] + psum[x-1][y-1][t];
- }
- ii f(int x, int y){
- int mac = c;
- for(int i = x; i <= r; i++){
- for(int j = y; j <= c; j++){
- if(skip[i][j]){
- mac = min(mac, j-1);
- }
- if(j > mac)
- break;
- if(1LL * (i - x + 1) * (j - y + 1) > h) break;
- if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
- return {i, j};
- }
- }
- return {-1, -1};
- }
- ii f2(int x, int y){
- ii ans = {-1, -1};
- ll qtd = 0;
- int mac = c;
- for(int i = x; i <= r; i++){
- for(int j = y; j <= c; j++){
- if(skip[i][j]){
- mac = min(mac, j-1);
- }
- if(j > mac)
- break;
- if(1LL * (i - x + 1) * (j - y + 1) > h) break;
- if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l){
- if(1LL * (i - x + 1) * (j - y + 1) > qtd){
- qtd = 1LL * (i - x + 1) * (j - y + 1);
- ans = {i, j};
- }
- }
- }
- }
- return ans;
- }
- ii f3(int x, int y){
- int mac = c;
- for(int i = x; i <= r; i++){
- for(int j = y; j <= c; j++){
- if(skip[i][j]){
- mac = min(mac, j-1);
- }
- if(j > mac)
- break;
- if(1LL * (i - x + 1) * (j - y + 1) > max(h*2/3,1)) break;
- if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
- return {i, j};
- }
- }
- return {-1, -1};
- }
- ii f4(int x, int y){
- int mac = c;
- for(int i = x; i <= r; i++){
- for(int j = y; j <= c; j++){
- if(skip[i][j]){
- mac = min(mac, j-1);
- }
- if(j > mac)
- break;
- if(1LL * (i - x + 1) * (j - y + 1) > max(h*3/4,1)) break;
- if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
- return {i, j};
- }
- }
- return {-1, -1};
- }
- int main(){
- scanf("%d %d", &r, &c);
- scanf("%d %d", &l, &h);
- for(int i = 1; i <= r; i++){
- for(int j = 1; j <= c; j++){
- char x;
- scanf(" %c", &x);
- mat[i][j] = x;
- }
- }
- for(int i = 1; i <= r; i++){
- for(int j = 1; j <= c; j++){
- psum[i][j][0] = mat[i][j] == 'M';
- psum[i][j][1] = mat[i][j] == 'T';
- psum[i][j][0] += psum[i][j-1][0] + psum[i-1][j][0] - psum[i-1][j-1][0];
- psum[i][j][1] += psum[i][j-1][1] + psum[i-1][j][1] - psum[i-1][j-1][1];
- }
- }
- ii ini = {1, 1};
- vector<pair<ii, ii>> ans[4];
- while(ini.ff <= r){
- ii fim = f(ini.ff, ini.ss);
- if(fim.ff == -1){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- else{
- ans[0].pb({ini, fim});
- for(int i = ini.ff; i <= fim.ff; i++){
- for(int j = ini.ss; j <= fim.ss; j++){
- skip[i][j] = 1;
- }
- }
- ini.ss = fim.ss + 1;
- }
- while(ini.ff <= r && skip[ini.ff][ini.ss]){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- }
- memset(skip, 0, sizeof skip);
- ini = {1, 1};
- while(ini.ff <= r){
- ii fim = f2(ini.ff, ini.ss);
- if(fim.ff == -1){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- else{
- ans[1].pb({ini, fim});
- for(int i = ini.ff; i <= fim.ff; i++){
- for(int j = ini.ss; j <= fim.ss; j++){
- skip[i][j] = 1;
- }
- }
- ini.ss = fim.ss + 1;
- }
- while(ini.ff <= r && skip[ini.ff][ini.ss]){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- }
- memset(skip, 0, sizeof skip);
- ini = {1, 1};
- while(ini.ff <= r){
- ii fim = f3(ini.ff, ini.ss);
- if(fim.ff == -1){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- else{
- ans[2].pb({ini, fim});
- for(int i = ini.ff; i <= fim.ff; i++){
- for(int j = ini.ss; j <= fim.ss; j++){
- skip[i][j] = 1;
- }
- }
- ini.ss = fim.ss + 1;
- }
- while(ini.ff <= r && skip[ini.ff][ini.ss]){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- }
- memset(skip, 0, sizeof skip);
- ini = {1, 1};
- while(ini.ff <= r){
- ii fim = f4(ini.ff, ini.ss);
- if(fim.ff == -1){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- else{
- ans[3].pb({ini, fim});
- for(int i = ini.ff; i <= fim.ff; i++){
- for(int j = ini.ss; j <= fim.ss; j++){
- skip[i][j] = 1;
- }
- }
- ini.ss = fim.ss + 1;
- }
- while(ini.ff <= r && skip[ini.ff][ini.ss]){
- ini.ss++;
- if(ini.ss > c){
- ini.ss = 1;
- ini.ff++;
- }
- }
- }
- ll sum1 = 0;
- int id = 0;
- for(int j = 0; j < 2; j++){
- ll sum = 0;
- for(auto i : ans[j]){
- ii a, b;
- tie(a, b) = i;
- sum += 1LL * (b.ff - a.ff + 1) * (b.ss - a.ss + 1);
- }
- if(sum > sum1){
- sum1 = sum;
- id = j;
- }
- }
- printf("%d\n", ans[id].size());
- for(auto i : ans[id]){
- ii a, b;
- tie(a, b) = i;
- printf("%d %d %d %d\n", a.ff - 1, a.ss - 1, b.ff - 1, b.ss - 1);
- }
- cerr << sum1 << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement