Cod sursa(job #2295158)

Utilizator nurof3nCioc Alex Andrei nurof3n Data 3 decembrie 2018 11:37:04
Problema Dreptunghiuri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>

using namespace std;

const int MAXN = 400;

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

int nrN[MAXN * MAXN + 1], nrM[MAXN * MAXN + 1];
int N, M;

int main()
{
    in >> N >> M;
//initializam numarul cu nr de dreptunghiuri cu laturile paralele cu grila
    long long nrsol = 1LL * N * (N - 1) / 2 * M * (M - 1) / 2;

    for (int l1 = 1; l1 < N; l1++)
        for (int l2 = 1; l1 + l2 < N; l2++)
            nrN[l1 * l2] += N - l1 - l2;
    for (int l1 = 1; l1 < M; l1++)
        for (int l2 = 1; l1 + l2 < M; l2++)
            nrM[l1 * l2] += M - l1 - l2;

    int maxp = (max(N, M) - 1) / 2, r = (max(N, M) - 1) % 2;
    maxp *= maxp + r;

    for(int l = 1; l <= maxp; ++l)
        nrsol += nrN[l] * nrM[l];

    out << nrsol;

    return 0;
}