Pagini recente » Cod sursa (job #2290225) | Cod sursa (job #3153366) | Cod sursa (job #990899) | Cod sursa (job #48383) | Cod sursa (job #2954836)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("teren.in");
ofstream fout("teren.out");
/**
n = 1000..2000 n x n x (log n) operatii
n = 200..500 n^3 operatii
n = 100 n^4
6 8 1
0 0 0 1 0 0 0 0
0 1 0 0 0 0 0 0 p
1 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 q
0 1 1 0 0 1 0 0
0 0 0 1 0 0 0 0
sume partiale pe coloane
0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 p
1 1 0 1 0 0 1 0
1 1 0 2 0 0 1 0 q
1 2 1 2 0 1 1 0
1 2 1 3 0 1 1 1
*/
int a[303][303], t[303], n, m, X;
void Citire()
{
int i,j;
fin >> n >> m >> X;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
{
fin >> a[i][j];
a[i][j] += a[i-1][j];
}
}
/// lungimea maxima a unei secvente din t
/// care are suma elementelor <= X
int LungMax(int t[], int n, int X)
{
int suma = 0, i, j, lenmax = 0;
j = 1;
for (i = 1; i <= n; i++)
{
suma += t[i];
while (suma > X)
{
suma -= t[j];
j++;
}
lenmax = max(lenmax, i - j + 1);
}
return lenmax;
}
void Rezolvare()
{
int p, q, L, j, amax = 0;
for (p = 1; p <= n; p++)
for (q = p; q <= n; q++)
{
/// construim t:
for (j = 1; j <= m; j++)
t[j] = a[q][j] - a[p - 1][j];
L = LungMax(t, m, X);
amax =max(amax,L * (q - p + 1)) ;
}
fout<<amax<<"\n";
}
int main()
{
int i,j;
Citire();
Rezolvare();
fout.close();
return 0;
}