#2970

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:
1. aflate pe linii distincte ale matricei;
2. aflate pe coloane distincte ale matricei;

Date de intrare

Fișierul paralele.in conține pe prima linie, separate prin câte un spațiu trei valori naturale, în ordine: T, N și M. Dacă T este 1 se rezolvă doar cerința 1, iar dacă T este 2 se rezolvă doar cerința 2. Începând cu linia a doua se află elementele matricei, o linie a matricei pe o linie a fișierului. Elementele de pe aceeași linie se separă prin câte un spațiu.

Date de ieșire

Fișierul paralele.out conține pe prima linie un număr natural reprezentând valoarea cerută.

Restricții și precizări

1 <= T <= 2
Pentru 30 de puncte se garantează că T = 1, N = 2, 2 ≤ M ≤ 500 și toate elementele 1 de pe oricare dintre linii, dacă există, formează o secvență compactă.
Pentru alte 30 de puncte se garantează că T = 2, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500 și pe oricare coloană sunt maximum două valori de 1 alăturate.
Pentru alte 9 puncte se garantează că T = 1, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500.
Pentru alte 9 puncte se garantează că T = 2, 2 ≤ N ≤ 500, 2 ≤ M ≤ 500.
Pentru alte 12 puncte se garantează că T = 1, 35.000 ≤ N ≤ 40.000 și 8 ≤ M ≤ 10.
În concurs s-au acordat 10 puncte din oficiu. Aici se acordă pentru exemplul din enunț.

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

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;
#define nMax 50010
#define mMax 1010

ifstream f("paralele.in");
ofstream g("paralele.out");

int n, m, t;
long long lin[nMax], col[mMax], lgCol[nMax];
bool a[mMax];
long long peLinii()
{
    int i, j, lg;
    long long total=0;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            f>>a[j];
        lg=0;
        for(j=1;j<=m+1;j++)
            if(a[j]==1)
                lg++;
            else lin[i]+=1LL*lg*(lg-1)/2, lg=0;
        total+=lin[i];
    }
    total=total*(total-1)/2;
    for(i=1;i<=n;i++)
        total-=1LL*lin[i]*(lin[i]-1)/2;
    return total;
}
long long peColoane()
{
    long long total=0;
    int i, j;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
            f>>a[j];
        for(j=1;j<=m+1;j++)
            if(a[j]==1)
                lgCol[j]++;
            else col[j]+=1LL*lgCol[j]*(lgCol[j]-1)/2, lgCol[j]=0;
    }
    for(j=1;j<=m;j++)
    {
        if(lgCol[j])
            col[j]+=1LL*lgCol[j]*(lgCol[j]-1)/2;
        total+=col[j];
    }
    total=total*(total-1)/2;
    for(j=1;j<=m;j++)
        total-=1LL*col[j]*(col[j]-1)/2;
    return total;
}
int main()
{
    f>>t>>n>>m;
    if(t==1)
        g<<peLinii()<<'\n';
    else
        g<<peColoane()<<'\n';
    return 0;
}