Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Codeforces 1200D - White Lines
- // Lúcio Cardoso
- #include <bits/stdc++.h>
- using namespace std;
- const int maxn = 2e3+10;
- char a[maxn][maxn];
- int linha[maxn][maxn], col[maxn][maxn];
- int prefL[maxn][maxn], prefC[maxn][maxn];
- int firstL[maxn], lastL[maxn];
- int firstC[maxn], lastC[maxn];
- int totL[maxn], totC[maxn];
- int main(void)
- {
- int n, k;
- scanf("%d %d", &n, &k);
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= n; j++)
- scanf(" %c", &a[i][j]);
- }
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= n; j++)
- {
- if (a[i][j] == 'B')
- {
- if (firstL[i] == 0) firstL[i] = j;
- if (firstC[j] == 0) firstC[j] = i;
- lastC[j] = i;
- }
- }
- for (int j = n; j >= 1; j--)
- if (a[i][j] == 'B')
- if (lastL[i] == 0) lastL[i] = j;
- }
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= n; j++)
- {
- if (firstL[i] >= j && lastL[i]-j < k)
- linha[i][j]++;
- if (!firstL[i])
- linha[i][j]++;
- if (firstC[j] && firstC[j] >= i && lastC[j]-i < k)
- col[i][j]++;
- if (!firstC[j])
- col[i][j]++;
- }
- }
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= n; j++)
- {
- prefL[i][j] = prefL[i][j-1] + col[i][j];
- prefC[i][j] = prefC[i-1][j] + linha[i][j];
- }
- }
- for (int i = 1; i <= n; i++)
- {
- bool ok = 1;
- for (int j = 1; j <= n; j++)
- if (a[i][j] == 'B')
- ok = 0;
- if (ok) totL[i] = totL[i-1]+1;
- else totL[i] = totL[i-1];
- }
- for (int i = 1; i <= n; i++)
- {
- bool ok = 1;
- for (int j = 1; j <= n; j++)
- if (a[j][i] == 'B')
- ok = 0;
- if (ok) totC[i] = totC[i-1]+1;
- else totC[i] = totC[i-1];
- }
- int ans = 0;
- for (int i = 1; i+k-1 <= n; i++)
- for (int j = 1; j+k-1 <= n; j++)
- 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]));
- printf("%d\n", ans);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement