Cod sursa(job #3342207)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 23 februarie 2026 13:03:49
Problema Matrix Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.42 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f ("matrix.in");
ofstream g ("matrix.out");

const int NMAX = 1000;
int M, N, A[NMAX+1][NMAX+1], T[NMAX+1][NMAX+1], F[26];
bool valid[NMAX+1][NMAX+1]; /// Daca matricea care se termina in coltul i,j este valida

void citire() {
    char c;
    f >> M >> N;
    for (int i=1; i<=M; i++)
        for (int j=1; j<=M; j++) {
            f >> c;
            //
            A[i][j] = c - 'a';
        }
    //
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++) {
            f >> c;
            F[c-'a']++;
        }
}

void solve() {
    for (int c=0; c<=25; c++)
        for (int i=1; i<=M; i++)
            for (int j=1; j<=M; j++) {
                T[i][j] = (A[i][j] == c) + T[i][j-1] + T[i-1][j] - T[i-1][j-1];
                //
                if (i >= N && j >= N) {
                    int ii = i - N + 1,
                        jj = j - N + 1,
                        S = T[i][j] - T[ii-1][j] - T[i][jj-1] + T[ii-1][jj-1];
                    if (S != F[c])
                        valid[i][j] = 1;
                } else
                    valid[i][j] = 1;
            }
}

int main(){
    citire();
    solve();
    //
    int sol = 0;
    for (int i=1; i<=M; i++)
        for (int j=1; j<=M; j++)
            sol += (1 - valid[i][j]);
    //
    g << sol;

    f.close();
    g.close();
    return 0;
}