Cod sursa(job #459897)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 31 mai 2010 15:08:21
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <iostream>
#include <fstream>
#define INFILE "teren.in"
#define OUTFILE "teren.out"
#define max_N 302
#define max_M 302

using namespace std;

ifstream fin(INFILE);
ofstream fout(OUTFILE);

int N, M, X, S[max_N][max_M]; // s[i][j] cu semnificatia ca <=i pe coloana j (nr de 1)
char A[max_N][max_M];
int i,j,k,l, val, max_area, V[max_M];

void precalculate()
{
	for(i = 1; i <= N; i ++)
		for(j = 1; j <= M; j ++)
			S[i][j] = S[i - 1][j] + A[i][j] - 48;
}
	
void solve()
{
	int st = 1, dr = 1;
	int suma = 0;
	for(int i = 1; i <= N; i ++)
		for(int j = 1; j <= N; j ++)
		{
			for(int k = 1; k <= M; k ++)
				V[k] = S[j][k] - S[i-1][k];
			st = 1;
			suma = 0;
			for(int dr = 1; dr <= M; dr ++)
				{
					suma += V[dr];
					while(st <= dr && suma > X)
					{
						suma -= V[st];
						st ++;
					}
					if(st <= dr)
						max_area = max(max_area, (j - i + 1) * (dr - st + 1));
				}
		}
	
}
	
int main()
{
	fin >> N >> M >> X;
	for(i = 1; i <= N; i ++)
		for(j = 1; j <= M; j ++)
			fin >> A[i][j];
	precalculate();
	solve();
	fout << max_area;
	return 0;
}