本蒟蒻#2#6#9WA掉惹,求各位大佬帮忙差错。对拍出来的hack数据如下:
input:
6 9 3
1 26 33 21 21 1 49 31 40
14 5 25 13 21 9 49 12 21
7 43 36 16 14 33 41 8 26
29 14 25 31 42 11 48 43 46
1 44 21 29 11 47 26 11 43
15 35 47 3 37 21 9 9 26
output
23
本蒟蒻的代码不知道为什么输出0了:
#include<bits/stdc++.h>
#define int long long
using namespace std;
int l,c,n,a[1005][1005];
int ans=1e10,xmx[1005][1005],xmn[1005][1005],ymx[1005][1005],ymn[1005][1005];
deque<int>dmx,dmn;
void duix(int x)
{
for(int i=1;i<n;i++)
{
while(!dmx.empty()&&a[x][dmx.back()]<a[x][i])
dmx.pop_back();
dmx.push_back(i);
while(!dmn.empty()&&a[x][dmn.back()]>a[x][i])
dmn.pop_back();
dmn.push_back(i);
}
if(n==1)
{
dmx.push_back(1);
xmx[x][1]=a[x][1];
dmn.push_back(1);
xmn[x][1]=a[x][1];
}
while(dmx.back()<c)
{
int num=dmx.back()+1;
while(!dmx.empty()&&a[x][dmx.back()]<a[x][num])
dmx.pop_back();
if(!dmx.empty()&&dmx.front()<num-n+1) dmx.pop_front();
dmx.push_back(num);
xmx[x][num]=a[x][dmx.front()];
while(!dmn.empty()&&a[x][dmn.back()]>a[x][num])
{
dmn.pop_back();
}
if(!dmn.empty()&&dmn.front()<num-n+1) dmn.pop_front();
dmn.push_back(num);
xmn[x][num]=a[x][dmn.front()];
}
return ;
}
void duiy(int x)
{
for(int i=1;i<n;i++)
{
while(!dmx.empty()&&xmx[dmx.back()][x]<xmx[i][x])
dmx.pop_back();
dmx.push_back(i);
while(!dmn.empty()&&xmn[dmn.back()][x]>xmn[i][x])
dmn.pop_back();
dmn.push_back(i);
}
if(n==1)
{
dmx.push_back(1);
ymx[x][1]=xmx[1][x];
dmn.push_back(1);
ymn[x][1]=xmn[1][x];
}
while(dmx.back()<l)
{
int num=dmx.back()+1;
while(!dmx.empty()&&xmx[dmx.back()][x]<xmx[num][x])
dmx.pop_back();
if(!dmx.empty()&&dmx.front()<num-n+1) dmx.pop_front();
dmx.push_back(num);
ymx[x][num]=xmx[dmx.front()][x];
while(!dmn.empty()&&xmn[dmn.back()][x]>xmn[num][x])
dmn.pop_back();
if(!dmn.empty()&&dmn.front()<num-n+1) dmn.pop_front();
dmn.push_back(num);
ymn[x][num]=xmn[dmn.front()][x];
}
return ;
}
signed main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%lld%lld%lld",&l,&c,&n);
if(n<=1)
{
printf("0\n");
return 0;
}
for(int i=1;i<=l;i++)
for(int j=1;j<=c;j++) scanf("%lld",&a[i][j]);
for(int i=1;i<=l;i++)
{
dmx.clear();
dmn.clear();
duix(i);
}
for(int i=1;i<=c;i++)
{
dmx.clear();
dmn.clear();
duiy(i);
}
for(int i=n;i<=l;i++)
for(int j=n;j<=c;j++)
if(ans>ymx[i][j]-ymn[i][j]) ans=ymx[i][j]-ymn[i][j];
printf("%lld",ans);
return 0;
}