Cod sursa(job #2078361)

Utilizator AlmaChan13Petria Mitran Alma Elena AlmaChan13 Data 29 noiembrie 2017 14:20:32
Problema Teren Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
using namespace std;
int i,j,k,p,nr,m,n,t,s[301][301],x,maxim=-1;
int main() {
    ifstream fin ("teren.in");
    ofstream fout("teren.out");

    fin>>n>>m>>x;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++) {
            fin>>t;
            s[i][j] = t + s[i-1][j];
        }

    /// s[i][j] = numarul de 1 care se afla pe coloana j de la linia i in sus

    for (i=1;i<=n;i++)
        for (j=i;j<=n;j++) {
            /// i si j joaca rol de linii si ma intereseaza cel mai bun dreptunghi cu maxim x de 1 sprijinit pe liniile i si j
            p = 1;
            nr = 0;
            for (k=1;k<=m;k++) {
                nr += s[j][k] - s[i-1][k];
                while (nr > x) {
                    nr -= (s[j][p] - s[i-1][p]);
                    p++;
                }
            }
            if ((j-i+1) * (k-p+1) > maxim) {
                maxim = (j-i+1) * (k-p+1);
            }
        }
    fout<<maxim;

    return 0;
}

/*

vector cu 0 si 1 si vreau sa aflu lungimea maxima a unei secvente cu maxim x de 1

p = 1;
for (i=1;i<=n;i++) {
    /// lungimea maxima a unei secvente ce contine maxim x de 1 si care se termina pe pozitia i
    if (v[i] == 1)
        nr++;

    while (nr > x) {
        if (v[p] == 1)
            nr--;
        p++;
    }

    if (i-p+1 > maxim)
        maxim = i-p+1;
}
*/