Cod sursa(job #3341417)

Utilizator PopRadGabPopescu Radu Gabriel PopRadGab Data 19 februarie 2026 15:09:16
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("matrix.in");
ofstream fout("matrix.out");

#define DIM 1001

char A[DIM][DIM];
int dp[DIM][DIM],ok[DIM][DIM];

int fr[256];

int main(){
    ios::sync_with_stdio(false);
    fin.tie(0);

    int n,m;
    fin>>n>>m;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            fin>>A[i][j];

    for(int i=1;i<=m;i++)
        for(int j=1;j<=m;j++){
            char ch;
            fin>>ch;
            fr[ch]++;
        }

        for(int i=m;i<=n;i++)
            for(int j=m;j<=n;j++)
                ok[i][j]=1;

    for(int ch='a';ch<='z';ch++){

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dp[i][j]=((A[i][j]==ch) ? 1 : 0)+dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];

        for(int i=m;i<=n;i++)
            for(int j=m;j<=n;j++)
                if((dp[i][j]-dp[i-m][j]-dp[i][j-m]+dp[i-m][j-m])!=fr[ch])
                    ok[i][j]=0;
    }
    int sol=0;
    for(int i=m;i<=n;i++)
        for(int j=m;j<=n;j++)
            sol+=ok[i][j];

    fout<<sol;
    return 0;
}