Pagini recente » Cod sursa (job #2545265) | Cod sursa (job #899404) | Cod sursa (job #318253) | Cod sursa (job #328785) | Cod sursa (job #2768736)
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
ifstream f("teren.in");
ofstream g("teren.out");
typedef long long ll;
typedef pair<int,int> pi;
int t,T;
int N,M,X;
const int dim=310;
int a[dim][dim],sum[dim][dim],prefix_col[dim][dim],dp[dim][dim][dim];
int sum_matrix(int i,int j,int width,int height)
{
return sum[i][j]-sum[i-height][j]-sum[i][j-width]+sum[i-height][j-width];
}
int CB(int st,int dr,int x,int i,int height)
{
int mij,ans=-1;
while(st<=dr)
{
mij=(st+dr)/2;
int sumc=sum_matrix(i,mij,mij-st+1,height);
// cout<<"BALANICI "<<i<<' '<<mij<<' '<<mij-i+1
if(sumc>=x)
{
ans=mij;
dr=mij-1;
}
else st=mij+1;
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int total=0;
f>>N>>M>>X;
for(int i=1;i<=N;i++)
for(int j=1;j<=M;j++)
{
f>>a[i][j];
prefix_col[i][j]=prefix_col[i-1][j]+a[i][j];
sum[i][j]=sum[i][j-1]+prefix_col[i][j];
}
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
int poz=j-1;
for(int height=i;height>=1;height--)
{
int width=dp[i][j-1][height];
int sumc=sum_matrix(i,j-1,width,height);
int adaos=prefix_col[i][j]-prefix_col[i-height][j];
if(sumc+adaos<=X)
{
dp[i][j][height]=dp[i][j-1][height]+1;
}
else
{
int erase_sum=sumc+adaos-X;
int rez=CB(j-width,poz,erase_sum,i,height); //coloana pt care dp[i][col][height] are suma >= erase_sum
dp[i][j][height]=dp[i][j-1][height]+1-(rez-(j-width)+1);
poz=rez;
}
total=max(total,dp[i][j][height]*height);
}
}
}
g<<total<<'\n';
return 0;
}