HELPPM - Giúp ngài thủ tướng!
Tác giả: hieult
Ngôn ngữ: C++
#include <stdio.h>
//#include <conio.h>
int main()
{
//freopen("1.in","r",stdin);
int n,m,area,a[502][502],x,x1,y1,x2,y2;
long long are = 0;
scanf("%d %d %d",&n,&m,&area);
for(int i = 0;i<m;i++)
a[0][i] = 0;
for(int i = 1;i<=n;i++)
{
a[i][0] = 0;
for(int j = 1;j<=m;j++)
{
scanf("%d",&x);
a[i][j] = a[i][j-1]+x;
are = are + x;
// printf("%d ",a[i][j]);
}
// printf("\n");
}
if(are<area)
printf("-1");
else
{
x1 = 1;y1=1;x2 = m;y2 = n; int min = n*m;
for(int i = 1;i<=n;i++)
for(int j = i;j<=n;j++)
{
int u = 1 , v = 1;long long tong = 0;
while(v<=n)
{
tong = tong + a[v][j] - a[v][i-1];
if(tong >=area)
{
if((v-u+1) * (j-i+1)<min)
{
min = (v-u+1) * (j-i+1);
x1 = i; y1 = u; x2 = j; y2 = v;
}
u++;
while(u<=v)
{
tong = tong - a[u-1][j]+a[u-1][i-1];
if(tong >=area)
{
if((v-u+1) * (j-i+1)<min)
{
min = (v-u+1) * (j-i+1);
x1 = i; y1 = u; x2 = j; y2 = v;
}
}
else break;
u++;
}
}
// printf("%d %d\n",u,v);
v++;
}
}
printf("%d\n%d %d %d %d",min,y1,x1,y2,x2);
}
// getch();
}