Cod sursa(job #1994591)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 25 iunie 2017 14:10:33
Problema Matrix Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <bits/stdc++.h>
#define Nmax 1001
using namespace std;
ifstream f("matrix.in");
ofstream g("matrix.out");
int b[26];
int D[Nmax][Nmax];
int S[Nmax][Nmax];
char a[Nmax][Nmax];
bitset < Nmax > still[Nmax];
int main()
{
    int n,m,ans,i,j,k;
    char ch;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>(a[i]+1);
    }
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
        {
            f>>ch;
            b[ch-'a']++;
        }
    ans=(n-m+1)*(n-m+1);
    for(k=0;k<26;k++)
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                D[i][j]=D[i-1][j]+D[i][j-1]-D[i-1][j-1];
                if(a[i][j]-'a'==k)
                    D[i][j]++;
            }
        for(i=m;i<=n;i++)
            for(j=m;j<=n;j++)
                if(!still[i][j])
                {
                    S[i][j]=D[i][j]-D[i-m][j]-D[i][j-m]+D[i-m][j-m];
                    if(S[i][j]!=b[k])
                    {
                        still[i][j]=1;
                        ans--;
                    }
                }
        memset(S, 0, sizeof(S));
    }
    g<<ans;

    return 0;
}