比赛 |
20140418 |
评测结果 |
AATTTTTTTT |
题目名称 |
滑雪场地的难度系数 |
最终得分 |
20 |
用户昵称 |
King |
运行时间 |
8.949 s |
代码语言 |
C++ |
内存使用 |
15.55 MiB |
提交时间 |
2014-04-18 09:21:35 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
#define MAXN 1000
struct point
{
int x,y;
}q[MAXN*MAXN];
ll ans;
int n,m,t,h[MAXN][MAXN],ermax,ti[MAXN][MAXN],tinow;
int check(int lim,int x,int y)
{
tinow++;int cnt=0,ql=1,qr=1;
ti[x][y]=tinow;cnt++;q[1].x=x;q[1].y=y;
while(ql<=qr)
{
point k=q[ql];
if(k.x>1 && ti[k.x-1][k.y]!=tinow && abs(h[k.x][k.y]-h[k.x-1][k.y])<=lim){q[++qr].x=k.x-1;q[qr].y=k.y;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
if(k.x<n && ti[k.x+1][k.y]!=tinow && abs(h[k.x][k.y]-h[k.x+1][k.y])<=lim){q[++qr].x=k.x+1;q[qr].y=k.y;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
if(k.y>1 && ti[k.x][k.y-1]!=tinow && abs(h[k.x][k.y]-h[k.x][k.y-1])<=lim){q[++qr].x=k.x;q[qr].y=k.y-1;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
if(k.y<m && ti[k.x][k.y+1]!=tinow && abs(h[k.x][k.y]-h[k.x][k.y+1])<=lim){q[++qr].x=k.x;q[qr].y=k.y+1;ti[q[qr].x][q[qr].y]=tinow;cnt++;}
ql++;
}
return cnt;
}
void work(int x,int y)
{
int el=0,er=ermax,re;
while(el<=er)
{
int mid=el+er>>1;
if(check(mid,x,y)>=t){re=mid;er=mid-1;}
else el=mid+1;
}
ans+=ll(re);
}
int main()
{
freopen("skilevel.in","r",stdin);
freopen("skilevel.out","w",stdout);
scanf("%d%d%d",&n,&m,&t);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&h[i][j]),ermax=ermax>h[i][j]?ermax:h[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int ha;
scanf("%d",&ha);
if(ha)work(i,j);
}
printf("%lld\n",ans);
return 0;
}