# Cod sursa(job #2447103)

Utilizator Data 12 august 2019 10:19:47 Struti 100 cpp-64 done Arhiva de probleme 2.21 kb
``````#include <cstdio>
#include<algorithm>

using namespace std;
int m,n,p,dx,dy,min1,ap;
int mat[1005][1005];
int dmx[1005],dmi[1005];
int m1[1005][1005],m2[1005][1005];
int m3[1005][1005];
void alg()
{
int i,j,f1,f2,l1,l2;
//deque pe linii
for(i=1; i<=m; i++)
{
f1=1;
l1=0;
f2=1;
l2=0;
for(j=1; j<=n; j++)
{
//minim

while(f1<=l1 && mat[i][j]<=mat[i][dmi[l1]])
l1--;
dmi[++l1]=j;
if(dmi[f1]<=j-dy)
f1++;
m1[i][j]=mat[i][dmi[f1]];

//maxim

while(f2<=l2 && mat[i][j]>=mat[i][dmx[l2]])
l2--;
dmx[++l2]=j;
if(dmx[f2]<=j-dy)
f2++;
m2[i][j]=mat[i][dmx[f2]];
}
}

//deque pe coloane pe care avem min,max

for(i=dy; i<=n; i++)
{
f1=1;
l1=0;
f2=1;
l2=0;
for(j=1; j<=m; j++)
{
//minim

while(f1<=l1 && m1[j][i]<=m1[dmi[l1]][i])
l1--;
dmi[++l1]=j;
if(dmi[f1]<=j-dx)
f1++;
m3[j][i]=0-m1[dmi[f1]][i];

//maxim

while(f2<=l2 && m2[j][i]>=m2[dmx[l2]][i])
l2--;
dmx[++l2]=j;
if(dmx[f2]<=j-dx)
f2++;
m3[j][i]+=m2[dmx[f2]][i];

if(j>=dx)
{
if(m3[j][i]<min1)
{
min1=m3[j][i];
ap=1;
}
else if(m3[j][i]==min1)
ap++;
}

}
}
}
int main()
{
freopen("struti.in","r",stdin);
freopen("struti.out","w",stdout);
int i,j;
scanf("%d%d%d",&m,&n,&p);
for(i=1; i<=m; i++)
for(j=1; j<=n; j++)
scanf("%d",&mat[i][j]);
for(i=1; i<=p; i++)
{
scanf("%d%d",&dx,&dy);
ap=0;
min1=2000000000;
alg();
if(dx!=dy)
{
swap(dx,dy);
alg();
}
printf("%d %d\n",min1,ap);
}
return 0;
}
``````