Cod sursa(job #1965267)

Utilizator shantih1Alex S Hill shantih1 Data 14 aprilie 2017 11:08:33
Problema Teren Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.3 kb
#include <iostream>
#include <fstream>

using namespace std;

long long n, m, i, j, s[303][303], z, k, nr, l, mx, cs, rez;

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++)
    {
         z = 0;
        for (i = 1; i <= n; i++)
        {   s[i][j] += z;    z = s[i][j];   }
    }

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

                    if (s[j][l]-s[i-1][l] <= k)
                    {
                        nr = 1;
                        cs = s[j][l]-s[i-1][l];
                    }
                    else
                    {
                        nr = 0;
                        cs = 0;
                    }
                }
            }

            if (nr > mx) mx = nr;
            if ((j-i+1)*mx > rez)        rez = (j-i+1)*mx;
        }
    }

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