Avem o matrice de dimensiuni N x M, cu elemente 0 și 1. Numim segment o secvență de cel puțin două valori 1 aflate una lângă alta, toate pe aceeași linie, sau toate pe aceeași coloană a matricei.

Cerința

Se cere determinarea numărului de perechi de segmente:

Exemplu

paralele.in

1 5 6
0 1 1 1 0 0
1 0 0 0 0 0
0 0 0 1 0 0
1 1 0 1 1 0
0 1 1 0 0 0

paralele.out

11

Explicație

Prima valoare din fișierul de intrare fiind 1, ne interesează segmente formate pe linii. Pe prima linie este o secvență de valori 1 formată din trei elemente. Ea produce trei segmente: cel cu primele două valori de 1, cel cu ultimele două valori de 1 și cel cu toate cele trei valori de 1. Pe linia a doua nu se găsește niciun segment, nefiind cel puțin două valori 1 alăturate. Pe linia a treia nu se găsește niciun segment, pe linia a patra sunt două segmente iar pe linia a cincea este un singur segment. Numărul cerut se obține astfel: fiecare dintre cele trei segmente de pe prima linie este paralel cu fiecare dintre segmentele de pe a patra și de pe a cincea linie iar segmentele de pe linia a patra sunt paralele cu segmentul de pe ultima linie. Pentru exemplul prezentat, dacă am fi avut T = 2 rezultatul calculat ar fi trebuit să fie 1 (segmentul de pe coloana a doua este paralel cu segmentul de pe coloana a patra).

#include <bits/stdc++.h>

using namespace std;

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

int a[501][501] , n , m , cer , x[40001];
int b[40001][11];
long long s;

int main()
{
    cin >> cer >> n >> m;
    if(n <= 500)
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= m ; j++)
                cin >> a[i][j];
        if(cer == 1)
        {
                for(int i = 1 ; i <= n ; i++)
                {
                    int l = 0;
                    for(int j = 1 ; j <= m ; j++)
                        if(a[i][j] == 1) l++;
                        else
                        {
                            x[i] += l*(l - 1) / 2;
                            l = 0;
                        }
                    x[i] += l*(l - 1) / 2;
                }
                for(int i = 1 ; i <= n ; i++)
                    for(int j = i + 1 ; j <= n ; j++)
                        s += 1ll * x[i] * x[j];
                cout << s;

        }
        else
        {
            for(int i = 1 ; i <= m ; i++)
            {
                int l = 0;
                for(int j = 1 ; j <= n ; j++)
                    if(a[j][i] == 1) l++;
                    else
                    {
                        x[i] += l*(l - 1) / 2;
                        l = 0;
                    }
                x[i] += l*(l - 1) / 2;
            }
            for(int i = 1 ; i <= m ; i++)
                for(int j = i + 1 ; j <= m ; j++)
                    s += 1ll * x[i] * x[j];
            cout << s;

        }
    }
    else
    {
        for(int i = 1 ; i <= n ; i++)
            for(int j = 1 ; j <= m ; j++)
                cin >> b[i][j];
        for(int i = 1 ; i <= n ; i++)
                {
                    int l = 0;
                    for(int j = 1 ; j <= m ; j++)
                        if(b[i][j] == 1) l++;
                        else
                        {
                            x[i] += l*(l - 1) / 2;
                            l = 0;
                        }
                    x[i] += l*(l - 1) / 2;
                }
        for(int i = 1 ; i <= n ; i++)
            s += x[i];
        s = s * (s - 1) / 2;
        for(int i = 1 ; i <= n ; i++)
            s -= 1ll * x[i] * (x[i] - 1) / 2;
        cout << s;
    }
    return 0;
}