Pagini recente » Cod sursa (job #1680228) | Cod sursa (job #2330747) | Cod sursa (job #1785504) | Cod sursa (job #1021138) | Cod sursa (job #504868)
Cod sursa(job #504868)
#include<fstream>
#define inf "teren.in"
#define outf "teren.out"
#define NMax 310
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
short N,M,X;
short T[NMax][NMax], S[NMax][NMax], A[NMax];
void read()
{
f>>N>>M>>X;
for(short i=1; i<=N; i++)
for(short j=1; j<=M; j++) f>>T[i][j]; // O(N*M)
}
inline short max(short a,short b) { return ( a>b ? a : b ); }
void solve()
{
//S[i][j] - nr de 1 de pe coloana j si liniile <= i
for(short j=1; j<=M; j++)
for(short i=1; i<=N; i++) S[i][j] = S[i-1][j] + T[i][j]; // O(N*M)
short max_area = 0;
for(short i=1; i<=N; i++)
for(short j=i; j<=N; j++) // O(N^2)
{
for(short k=1; k<=M; k++) A[k] = S[j][k] - S[i-1][k]; // O(M)
short st = 1, suma = 0;
for(short dr=1; dr<=M; dr++) // O(M)
{
suma += A[dr];
while( st<=dr && suma>X ) suma -= A[st], st++;
if( st<=dr ) max_area = max( max_area, (j-i+1)*(dr-st+1) );
}
}
// --> O( N^2 * M )
g<< max_area;
}
int main()
{
read(); solve();
f.close(); g.close();
return 0;
}