Cod sursa(job #998332)

Utilizator alex_unixPetenchea Alexandru alex_unix Data 16 septembrie 2013 19:52:02
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb

#include <cstdio>

const int MAX_SIZE(405);

int n, m;
long long Matrix [MAX_SIZE] [MAX_SIZE];
long long Result;
int Root [MAX_SIZE * MAX_SIZE];

inline void Read (void)
{
	std::freopen("dreptunghiuri.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	std::fclose(stdin);
}

inline void Print (void)
{
	std::freopen("dreptunghiuri.out","w",stdout);
	std::printf("%lld\n",Result);
	std::fclose(stdout);
}

inline void Preprocess (void)
{
	for (int i(1) ; i < MAX_SIZE ; ++i)
		Root[i * i] = i;
	--n;
	--m;
}

inline void Compute (void)
{
	int h, w, x1, x2, l, d, sum;
	for (h = 1 ; h <= n ; ++h)
		for (w = 1 ; w <= m ; ++w)
		{
			if (Matrix[w][h])
				sum = Matrix[w][h];
			else
			{
				for (l = sum = 0 ; l < h ; ++l)
				{
					d = w * w - 4 * l * (h - l);
					if (d < 0 || (d && !Root[d]))
						continue;
					d = Root[d];
					x1 = x2 = -1;
					if ((w + d) % 2 == 0)
						x1 = (w + d) / 2;
					if ((w - d) % 2 == 0)
						x2 = (w - d) / 2;
					if (x1 >= 0 && x1 < w)
						++sum;
					if (x2 != x1 && x2 >= 0 && x2 < w)
						++sum;
				}
				Matrix[h][w] = sum;
			}
			Result += (n - h + 1) * (m - w + 1) * sum;
		}
}

int main (void)
{
	Read();
	Preprocess();
	Compute();
	Print();
	return 0;
}