Cod sursa(job #740041)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 24 aprilie 2012 16:28:22
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <fstream>
using namespace std;

#define maxSize 301

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

int rows,columns;
int maxBad,maxArea;
int best[maxSize][maxSize];

int main() {
    in >> rows >> columns >> maxBad;

    bool value;
    for(int i=1;i<=rows;i++)
        for(int k=1;k<=columns;k++) {
            in >> value;
            best[i][k] = best[i-1][k] + value;
        }

    for(int i=1;i<=rows;i++)
        for(int k=i;k<=rows;k++) {
            int left = 1;
            int right = 0;
            int sum = 0;

            while(right < columns) {
                sum += best[k][++right] - best[i-1][right];

                while(sum > maxBad)
                    sum -= best[k][left] - best[i-1][left++];

                if((k-i+1) * (right-left+1) > maxArea)
                    maxArea = (k-i+1) * (right-left+1);
            }
        }

    out << maxArea << "\n";

    in.close();
    out.close();

    return (0);
}