Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2019
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.80 KB | None | 0 0
  1. // Codeforces 1200D - White Lines
  2. // Lúcio Cardoso
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. using namespace std;
  7.  
  8. const int maxn = 2e3+10;
  9.  
  10. char a[maxn][maxn];
  11.  
  12. int linha[maxn][maxn], col[maxn][maxn];
  13. int prefL[maxn][maxn], prefC[maxn][maxn];
  14.  
  15. int firstL[maxn], lastL[maxn];
  16. int firstC[maxn], lastC[maxn];
  17.  
  18. int totL[maxn], totC[maxn];
  19.  
  20. int main(void)
  21. {
  22. int n, k;
  23. scanf("%d %d", &n, &k);
  24.  
  25. for (int i = 1; i <= n; i++)
  26. {
  27. for (int j = 1; j <= n; j++)
  28. scanf(" %c", &a[i][j]);
  29. }
  30.  
  31. for (int i = 1; i <= n; i++)
  32. {
  33. for (int j = 1; j <= n; j++)
  34. {
  35. if (a[i][j] == 'B')
  36. {
  37. if (firstL[i] == 0) firstL[i] = j;
  38. if (firstC[j] == 0) firstC[j] = i;
  39.  
  40. lastC[j] = i;
  41. }
  42. }
  43.  
  44. for (int j = n; j >= 1; j--)
  45. if (a[i][j] == 'B')
  46. if (lastL[i] == 0) lastL[i] = j;
  47. }
  48.  
  49. for (int i = 1; i <= n; i++)
  50. {
  51. for (int j = 1; j <= n; j++)
  52. {
  53. if (firstL[i] >= j && lastL[i]-j < k)
  54. linha[i][j]++;
  55. if (!firstL[i])
  56. linha[i][j]++;
  57.  
  58. if (firstC[j] && firstC[j] >= i && lastC[j]-i < k)
  59. col[i][j]++;
  60. if (!firstC[j])
  61. col[i][j]++;
  62. }
  63. }
  64.  
  65. for (int i = 1; i <= n; i++)
  66. {
  67. for (int j = 1; j <= n; j++)
  68. {
  69. prefL[i][j] = prefL[i][j-1] + col[i][j];
  70. prefC[i][j] = prefC[i-1][j] + linha[i][j];
  71. }
  72. }
  73.  
  74. for (int i = 1; i <= n; i++)
  75. {
  76. bool ok = 1;
  77. for (int j = 1; j <= n; j++)
  78. if (a[i][j] == 'B')
  79. ok = 0;
  80.  
  81. if (ok) totL[i] = totL[i-1]+1;
  82. else totL[i] = totL[i-1];
  83. }
  84.  
  85. for (int i = 1; i <= n; i++)
  86. {
  87. bool ok = 1;
  88. for (int j = 1; j <= n; j++)
  89. if (a[j][i] == 'B')
  90. ok = 0;
  91.  
  92. if (ok) totC[i] = totC[i-1]+1;
  93. else totC[i] = totC[i-1];
  94. }
  95.  
  96. int ans = 0;
  97.  
  98. for (int i = 1; i+k-1 <= n; i++)
  99. for (int j = 1; j+k-1 <= n; j++)
  100. ans = max(ans, prefL[i][j+k-1]-prefL[i][j-1] + prefC[i+k-1][j]-prefC[i-1][j] + totL[n]-(totL[i+k-1]-totL[i-1]) + totC[n]-(totC[j+k-1]-totC[j-1]));
  101.  
  102. printf("%d\n", ans);
  103. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement