Cod sursa(job #2447107)

Utilizator miguelMihail Lavric miguel Data 12 august 2019 10:53:03
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.93 kb
/*
░░░░░░░░░░░░░░░░▄▄█▀▀██▄▄░░░░░░░
░░░░░░░░░░░░░▄█▀▀░░░░░░░▀█░░░░░░
░░░░░░░░░░░▄▀░░░░░░░░░░░░░█░░░░░
░░░░░░░░░▄█░░░░░░░░░░░░░░░█░░░░░
░░░░░░░██▀░░░░░░░▄▄▄░░▄░█▄█▄░░░░
░░░░░▄▀░░░░░░░░░░████░█▄██░▀▄░░░
░░░░█▀░░░░░░░░▄▄██▀░░██░██░██░░░
░░░█▀░░░░░░░░░▀█░▀█▀█▀▀▄██▄█▀░░░
░░░██░░░░░░░░░░█░░██░░░▀▀▄█▀░░░░
░░░░█░░░░░█░░░▀█░░░░░░░░░░▄█░░░░
░░░░▀█░░░░███▄░█░░░░░░▄▄▄▄█▀█▄░░
░░░░░▀██░░█▄▀▀██░░░░░░░░▄▄█░░▀▄░
░░░░░░▀▀█▄░▀▄▄░▄░░░░░░░███▀░░▄██
░░░░░░░░░▀▀▀███▀█▄░░░░░█▀░▀░░░▀█
░░░░░░░░░░░░▄▀░░░▀█▄░░░░░▄▄░░▄█▀
░░░▄▄▄▀▀▀▀▀█▀░░░░░█▄▀▄▄▄▄▄▄█▀▀░░
░▄█░░░▄██▀░░░░░░░░░█▄░░░░░░░░░░░
█▀▀░▄█░░░░░░░░░░░░░░▀▀█▄░░░░░░░░
█░░░█░░░░░░░░░░░░░░░░░░█▄░░░░░░░
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define x first
#define y second
#define pi pair <int, int>
#define vi vector <int>
//#define =1e9 =(int)1e9
const ll mod = 1000000007;
const ll nmax=1000003;
#define int ll
int n, k;
bool ctrl;
char t[2002][2002];
int rows[2002], cols[2002]; //white de la inceput
int mn[2002], mx[2002], mn1[2002], mx1[2002], ans;
int cur[2002][2002], cur1[2002][2002];

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>k;
    for(int i=1; i<=n; i++){
        ctrl=1;
        for(int j=1; j<=n; j++){
            char c;
            cin>>c;
            t[i][j]=c;
            if(c=='B'){
                ctrl=0;
                if(mn[i]==0) mn[i]=j;
                mx[i]=j;
            }
        }
        rows[i]=rows[i-1]+ctrl;
    }

    for(int j=1; j<=n; j++){
        ctrl=1;
        for(int i=1; i<=n; i++){
            char c=t[i][j];
            if(c=='B'){
                ctrl=0;
                if(mn1[j]==0) mn1[j]=i;
                mx1[j]=i;
            }
        }
        cols[j]=cols[j-1]+ctrl;
    }
    for(int i=1; i<=n; i++){
        if(mn[i]){
            for(int j=min(1LL, mx[i]); j<=max(mn[i]+k-1, n); j++) cur[i][j]++;
        }
        if(i>k && mn[i-k]) for(int j=min(1LL, mx[i-k]); j<=max(mn[i-k]+k-1, n); j++) cur[i][j]--;
        for(int j=1; j<=n; j++) cur[i][j]+=cur[i-1][j];
    }
   // dbg(mn[2]); dbg(mx[2]);
    for(int i=1; i<=n; i++){for(int j=1; j<=n; j++) cout<<cur[i][j]<<" "; cout<<endl;}

    for(int j=1; j<=n; j++){
        if(mn1[j]){
            for(int i=min(1LL, mx1[j]); i<=max(mn1[j]+k-1, n); i++) cur1[i][j]++;
        }
        if(j>k && mn1[j-k]) for(int i=min(1LL, mx1[j-k]); i<=max(mn1[j-k]+k-1, n); i++) cur1[i][j]--;
        for(int i=1; i<=n; i++) cur1[i][j]+=cur1[i][j-1];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            ans=max(ans, cur[i][j]+cur1[i][j]);
        }
    }
    cout<<ans<<endl;
    cout<<ans+rows[n]+cols[n];
}