Cod sursa(job #677754)

Utilizator milijrCristian Militaru milijr Data 10 februarie 2012 16:46:24
Problema Teren Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#include <iostream>
#include <stdio.h>

using namespace std;

#define MAXN 305

int teren[MAXN][MAXN], n, m;
int sir[MAXN];

int main()
{
	FILE *in = fopen("teren.in", "r");
	FILE *out= fopen("teren.out","w");
	int i, j, k;
	fscanf(in, "%i %i %i", &n, &m, &k);
	for(i = 1; i <= n; i++)
		for(j = 1; j <= m; j++)
		{
			fscanf(in, "%i", &teren[i][j]);
			teren[i][j] += teren[i - 1][j];
		}
	
	int l1, l2, s = 0, nr, dimMax = 0, dim, st, dr, dimf;
	for(l1 = 1; l1 <= n; l1 ++)
		for(l2 = l1; l2 <= n; l2 ++)
		{
            st = 1;
            dr = 0;
            dim = 0;
			for(i = 1; i <= m; i++)
			{
				nr = teren[l2][i] - teren[l1 - 1][i];
				sir[++dr] = nr;
				s += nr;
				while(s > k)
				{
                        s -= sir[st];
                        st++;
                        }
				dimf = (dr - st + 1) * (l2 - l1 + 1);
				if(dimf > dimMax)
					dimMax = dimf;
			}
			s = 0;
		}
	fprintf(out, "%i", dimMax);
}