Cod sursa(job #1965336)

Utilizator shantih1Alex S Hill shantih1 Data 14 aprilie 2017 12:13:50
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <iostream>
#include <fstream>

using namespace std;

int n, m, i, j, s[302][302], k, nr, l, mx, cs, rez, dr, st;

int main () {

    ifstream fin("teren.in");
    ofstream fout("teren.out");

    fin >> n >> m >> k;
    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++) fin >> s[i][j];

    for (j = 1; j <= m; j++)
        for (i = 1; i <= n; i++)
            s[i][j] += s[i-1][j];

    rez = -1;
    for (i = 1; i <= n; i++)
        for (j = i; j <= n; j++)
        {
            cs = 0;
            mx = 0;
            nr = 0;
            st = 1;
            for (l = 1; l <= m; l++)
            {
                cs += s[j][l]-s[i-1][l];
                if (cs <= k) {   nr++;   }
                else
                {
                    if (nr > mx) mx = nr;
                    while (cs > k)
                    {
                        cs -= s[j][st]-s[i-1][st];
                        st++;
                        nr--;
                    }
                    nr++;
                }
            }
            if (nr > mx) mx = nr;
            if ((j-i+1)*mx > rez)        rez = (j-i+1)*mx;
        }

    fout << rez << "\n";
}