Advertisement
Guest User

Untitled

a guest
Feb 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.44 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ii = pair<int, int>;
  6. #define ff first
  7. #define ss second
  8. #define pb push_back
  9.  
  10. const int N = 1005;
  11.  
  12. int psum[N][N][2];
  13. char mat[N][N];
  14. bool skip[N][N];
  15. int r, c;
  16. int l, h;
  17.  
  18. int soma(int i, int j, int x, int y, int t){
  19.     return psum[i][j][t] - psum[x-1][j][t] - psum[i][y-1][t] + psum[x-1][y-1][t];
  20. }
  21.  
  22. ii f(int x, int y){
  23.     int mac = c;
  24.     for(int i = x; i <= r; i++){
  25.         for(int j = y; j <= c; j++){
  26.             if(skip[i][j]){
  27.                 mac = min(mac, j-1);
  28.             }
  29.             if(j > mac)
  30.                 break;
  31.             if(1LL * (i - x + 1) * (j - y + 1) > h) break;
  32.             if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
  33.                 return {i, j};
  34.         }
  35.     }
  36.     return {-1, -1};
  37. }
  38.  
  39. ii f2(int x, int y){
  40.     ii ans = {-1, -1};
  41.     ll qtd = 0;
  42.     int mac = c;
  43.     for(int i = x; i <= r; i++){
  44.         for(int j = y; j <= c; j++){
  45.             if(skip[i][j]){
  46.                 mac = min(mac, j-1);
  47.             }
  48.             if(j > mac)
  49.                 break;
  50.             if(1LL * (i - x + 1) * (j - y + 1) > h) break;
  51.             if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l){
  52.                 if(1LL * (i - x + 1) * (j - y + 1) > qtd){
  53.                     qtd = 1LL * (i - x + 1) * (j - y + 1);
  54.                     ans = {i, j};
  55.                 }
  56.             }
  57.         }
  58.     }
  59.     return ans;
  60. }
  61.  
  62. ii f3(int x, int y){
  63.     int mac = c;
  64.     for(int i = x; i <= r; i++){
  65.         for(int j = y; j <= c; j++){
  66.             if(skip[i][j]){
  67.                 mac = min(mac, j-1);
  68.             }
  69.             if(j > mac)
  70.                 break;
  71.             if(1LL * (i - x + 1) * (j - y + 1) > max(h*2/3,1)) break;
  72.             if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
  73.                 return {i, j};
  74.         }
  75.     }
  76.     return {-1, -1};
  77. }
  78.  
  79. ii f4(int x, int y){
  80.     int mac = c;
  81.     for(int i = x; i <= r; i++){
  82.         for(int j = y; j <= c; j++){
  83.             if(skip[i][j]){
  84.                 mac = min(mac, j-1);
  85.             }
  86.             if(j > mac)
  87.                 break;
  88.             if(1LL * (i - x + 1) * (j - y + 1) > max(h*3/4,1)) break;
  89.             if(soma(i, j, x, y, 0) >= l && soma(i, j, x, y, 1) >= l)
  90.                 return {i, j};
  91.         }
  92.     }
  93.     return {-1, -1};
  94. }
  95.  
  96. int main(){
  97.     scanf("%d %d", &r, &c);
  98.     scanf("%d %d", &l, &h);
  99.     for(int i = 1; i <= r; i++){
  100.         for(int j = 1; j <= c; j++){
  101.             char x;
  102.             scanf(" %c", &x);
  103.             mat[i][j] = x;
  104.         }
  105.     }
  106.  
  107.     for(int i = 1; i <= r; i++){
  108.         for(int j = 1; j <= c; j++){
  109.             psum[i][j][0] = mat[i][j] == 'M';
  110.             psum[i][j][1] = mat[i][j] == 'T';
  111.             psum[i][j][0] += psum[i][j-1][0] + psum[i-1][j][0] - psum[i-1][j-1][0];
  112.             psum[i][j][1] += psum[i][j-1][1] + psum[i-1][j][1] - psum[i-1][j-1][1];
  113.         }
  114.     }
  115.  
  116.  
  117.     ii ini = {1, 1};
  118.     vector<pair<ii, ii>> ans[4];
  119.     while(ini.ff <= r){
  120.         ii fim = f(ini.ff, ini.ss);
  121.         if(fim.ff == -1){
  122.             ini.ss++;  
  123.             if(ini.ss > c){
  124.                 ini.ss = 1;
  125.                 ini.ff++;
  126.             }
  127.         }
  128.         else{
  129.             ans[0].pb({ini, fim});
  130.             for(int i = ini.ff; i <= fim.ff; i++){
  131.                 for(int j = ini.ss; j <= fim.ss; j++){
  132.                     skip[i][j] = 1;
  133.                 }
  134.             }
  135.             ini.ss = fim.ss + 1;
  136.         }
  137.         while(ini.ff <= r && skip[ini.ff][ini.ss]){
  138.             ini.ss++;
  139.             if(ini.ss > c){
  140.                 ini.ss = 1;
  141.                 ini.ff++;
  142.             }
  143.         }
  144.     }
  145.    
  146.     memset(skip, 0, sizeof skip);
  147.  
  148.     ini = {1, 1};
  149.     while(ini.ff <= r){
  150.         ii fim = f2(ini.ff, ini.ss);
  151.         if(fim.ff == -1){
  152.             ini.ss++;  
  153.             if(ini.ss > c){
  154.                 ini.ss = 1;
  155.                 ini.ff++;
  156.             }
  157.         }
  158.         else{
  159.             ans[1].pb({ini, fim});
  160.             for(int i = ini.ff; i <= fim.ff; i++){
  161.                 for(int j = ini.ss; j <= fim.ss; j++){
  162.                     skip[i][j] = 1;
  163.                 }
  164.             }
  165.             ini.ss = fim.ss + 1;
  166.         }
  167.         while(ini.ff <= r && skip[ini.ff][ini.ss]){
  168.             ini.ss++;
  169.             if(ini.ss > c){
  170.                 ini.ss = 1;
  171.                 ini.ff++;
  172.             }
  173.         }
  174.     }
  175.  
  176.     memset(skip, 0, sizeof skip);
  177.  
  178.     ini = {1, 1};
  179.     while(ini.ff <= r){
  180.         ii fim = f3(ini.ff, ini.ss);
  181.         if(fim.ff == -1){
  182.             ini.ss++;  
  183.             if(ini.ss > c){
  184.                 ini.ss = 1;
  185.                 ini.ff++;
  186.             }
  187.         }
  188.         else{
  189.             ans[2].pb({ini, fim});
  190.             for(int i = ini.ff; i <= fim.ff; i++){
  191.                 for(int j = ini.ss; j <= fim.ss; j++){
  192.                     skip[i][j] = 1;
  193.                 }
  194.             }
  195.             ini.ss = fim.ss + 1;
  196.         }
  197.         while(ini.ff <= r && skip[ini.ff][ini.ss]){
  198.             ini.ss++;
  199.             if(ini.ss > c){
  200.                 ini.ss = 1;
  201.                 ini.ff++;
  202.             }
  203.         }
  204.     }
  205.  
  206.     memset(skip, 0, sizeof skip);
  207.  
  208.     ini = {1, 1};
  209.     while(ini.ff <= r){
  210.         ii fim = f4(ini.ff, ini.ss);
  211.         if(fim.ff == -1){
  212.             ini.ss++;  
  213.             if(ini.ss > c){
  214.                 ini.ss = 1;
  215.                 ini.ff++;
  216.             }
  217.         }
  218.         else{
  219.             ans[3].pb({ini, fim});
  220.             for(int i = ini.ff; i <= fim.ff; i++){
  221.                 for(int j = ini.ss; j <= fim.ss; j++){
  222.                     skip[i][j] = 1;
  223.                 }
  224.             }
  225.             ini.ss = fim.ss + 1;
  226.         }
  227.         while(ini.ff <= r && skip[ini.ff][ini.ss]){
  228.             ini.ss++;
  229.             if(ini.ss > c){
  230.                 ini.ss = 1;
  231.                 ini.ff++;
  232.             }
  233.         }
  234.     }
  235.  
  236.     ll sum1 = 0;
  237.     int id = 0;
  238.     for(int j = 0; j < 2; j++){
  239.         ll sum = 0;
  240.         for(auto i : ans[j]){
  241.             ii a, b;
  242.             tie(a, b) = i;
  243.             sum += 1LL * (b.ff - a.ff + 1) * (b.ss - a.ss + 1);
  244.         }
  245.         if(sum > sum1){
  246.             sum1 = sum;
  247.             id = j;
  248.         }
  249.     }
  250.     printf("%d\n", ans[id].size());
  251.     for(auto i : ans[id]){
  252.         ii a, b;
  253.         tie(a, b) = i;
  254.         printf("%d %d %d %d\n", a.ff - 1, a.ss - 1, b.ff - 1, b.ss - 1);
  255.     }
  256.     cerr << sum1 << endl;
  257.  
  258.     return 0;
  259. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement