Cod sursa(job #822832)

Utilizator cristianalex81Cristian Alexandru cristianalex81 Data 24 noiembrie 2012 03:23:28
Problema Dreptunghiuri Scor 100
Compilator cpp Status done
Runda Lista lui wefgef Marime 1.54 kb
#include <fstream>
#include <string.h>
#include <cmath>
#define MAX_L 400

using namespace std;
typedef unsigned long long u64;

int rad[MAX_L * MAX_L + 1];
u64 sum[MAX_L + 1][MAX_L + 1];

int main(void)
{
        int m;
        int n;
        int cnt = 0;
        u64 result = 0;
	
        int d, r, q;
        double z;

	ifstream cin("dreptunghiuri.in");
	ofstream cout("dreptunghiuri.out");

        cin >> m >> n;
        for (d = 1; d <= MAX_L * MAX_L; ++d) {
            z = sqrt(double(d));
            if (z != int(z))
                rad[d] = int(1e5);
            else
                rad[d] = int(z);
        }
        for (int h = 1; h < m; ++h)
            for (int w = 1; w < n; ++w) {
                if (sum[h][w] > 0) {
                    result += sum[h][w];
                    continue;
                }
                cnt = 1;
                for (int i = 1; i <= h >> 1; ++i) {
                    d = w*w - 4*i*(h-i);
                    if (d < 0)
                        continue;
                    r = (w + rad[d]) >> 1;
                    if (0 < r && r < w)
                        cnt += 1 + (i + i < h);
                    if (rad[d] > 0) {
                        q = (w - rad[d]) >> 1;
                            if (0 < q && q < w)
                                cnt += 1 + (i + i < h);
                    }
                }
                sum[h][w] = (u64)cnt * (m-h) * (n-w);
                sum[w][h] = (u64)cnt * (m-w) * (n-h);
                result += sum[h][w];
            }
            cout << result <<'\n';
	return 0;
}