Cod sursa(job #3291519)

Utilizator florinul1Iuhas Florin florinul1 Data 4 aprilie 2025 23:30:23
Problema Matrix Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>
#include <bitset>

using namespace std;

const int N = 1e3 + 5;
char a[N][N];
int b[50], n, m, dp[N][N], sol;
bitset<N> ok[N];

void citire() {
	ifstream fin("matrix.in");
	fin >> m >> n;
	for (int i = 1; i <= m; i++)fin >> a[i];
	for (int i = 0; i <= n; i++) {
		fin.get();
		char ch;
		for (int j = 0; j < n; j++) {
			fin >> ch;
			b[ch]++;
		}
	}
	fin.close();
	for (int I = 'a'; I <= 'z'; I++) {
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= m; j++) {
				dp[i][j] = (a[i][j] == I) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
			}
		for (int i = n; i <= m; i++)
			for (int j = n; j <= m; j++) {
				if (dp[i][j] - dp[i - n][j] - dp[i][j - n] + dp[i - n][j - n] == b[I])ok[i][j]=1;
			}
	}
	for (int i = n; i <= m; i++)
		for (int j = n; j <= m; j++) {
			sol += ok[i][j];
		}
	ofstream fout("matrix.out");
	fout << sol;
	fout.close();
}

int main()
{
	citire();
	return  0;
}