Cod sursa(job #1827743)

Utilizator BlackNestaAndrei Manaila BlackNesta Data 12 decembrie 2016 11:28:15
Problema Matrix Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <bits/stdc++.h>
#define Nmax 1000

using namespace std;

int N, M;
char a[Nmax][Nmax], b[Nmax][Nmax];
int sum[Nmax][Nmax], sump[Nmax][Nmax];
int ans;

inline void Read()
{
    ifstream f("matrix.in");
    f >> N >> M;
    int i;
    for(i = 1; i <= N; i++)
        f >> (a[i] + 1);
    for(i = 1; i <= M; i++)
        f >> (b[i] + 1);
    f.close();
}

inline void Solve()
{
    int i, j, x;
    long long s, sp, S, SP;
    S = SP = 0;
    for(i = 1; i <= M; i++)
        for(j = 1; j <= M; j++)
        {
            x = b[i][j] - 'a' + 1;
            S += x;
            SP += (x * x);
        }
    ///cout << S << " " << SP << "\n\n";
    for(i = 1; i <= N; i++)
        for(j = 1; j <= N; j++)
        {
            x = a[i][j] - 'a' + 1;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] +
                        x - sum[i - 1][j - 1];
            sump[i][j] = sump[i - 1][j] + sump[i][j - 1] +
                         x * x - sump[i - 1][j - 1];
        }
    for(i = M; i <= N; i++)
        for(j = M; j <= N; j++)
        {
           s = sum[i][j] - sum[i - M][j] - sum[i][j - M] +
               sum[i - M][j - M];
           sp = sump[i][j] - sump[i - M][j] - sump[i][j - M] +
                sump[i - M][j - M];
           ///cout << s << " " << sp << "\n";
           if(s == S && sp == SP)
                ans++;
           ///cout << ans << "\n";
        }
    ///cout << ans << "\n";
}

inline void Write()
{
    ofstream g("matrix.out");
    g << ans << "\n";
    g.close();
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}