Pagini recente » Istoria paginii utilizator/corina.condurachi | Cod sursa (job #1549632) | Cod sursa (job #2149807) | Rating Florin Smeu (JohnnyKite) | Cod sursa (job #1703936)
#include <iostream>
#include <fstream>
#include <bitset>
using namespace std;
ifstream in("teren.in");
ofstream out("teren.out");
const int maxn = 305;
bitset <maxn> M[maxn];
int splin[maxn][maxn];
int spcol[maxn][maxn];
int sp[maxn][maxn];
int n, m, x;
void prec()
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
splin[i][j] = splin[i][j-1] + M[i][j];
for(int j = 1; j <= m; j++)
for(int i = 1; i <= n; i++)
spcol[i][j] = spcol[i-1][j] + M[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
sp[i][j] = sp[i-1][j-1] + splin[i][j] + spcol[i][j] - M[i][j];
}
inline int aflare_sum(int x1, int y1, int x2, int y2)
{
return sp[x2][y2] - sp[x1-1][y2] - sp[x2][y1-1] + sp[x1-1][y1-1];
}
inline int cautbin(int x1, int y1, int x2)
{
int st = y1;
int dr = m;
int ret = -1;
while(st <= dr)
{
int mij = (st + dr) / 2;
if(aflare_sum(x1, y1, x2, mij) > x)
dr = mij - 1;
else
{
ret = mij;
st = mij + 1;
}
}
return ret;
}
int main()
{
in >> n >> m >> x;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= m; j++)
{
int aux;
in >> aux;
M[i][j] = aux;
}
}
prec();
int mx = 0;
for(int x1 = 1; x1 <= n; x1++)
{
for(int y1 = 1; y1 <= m; y1++)
{
for(int x2 = x1; x2 <= n; x2++)
{
int y2 = cautbin(x1, y1, x2);
mx = max(mx, (x2 - x1 + 1) * (y2 - y1 + 1));
}
}
}
out << mx << "\n";
return 0;
}