比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 Suke 运行时间 9.001 s
代码语言 C++ 内存使用 3.42 MiB
提交时间 2014-04-18 11:23:30
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
bool v[502][502];
int a[502][502];
int q[250001][2];
int n,m,inf,t;
bool ok(int sx,int sy,long long de,int num){
	memset(v,0,sizeof(v));
    int l=1,r=1,k,x,y,ans=1,xx,yy;;
    v[sx][sy]=1;
    q[1][0]=sx;q[1][1]=sy;
    while(l<=r){
    	x=q[l][0];y=q[l][1];l++;
    	for(k=0;k<4;++k)
    	{
    	   xx=x+dx[k];yy=y+dy[k];
		   if (xx>0 && xx<=n && yy>0 && yy<=m)
		    if (!v[xx][yy])
		    if (abs(a[x][y]-a[xx][yy])<=de)
		    {
		    	v[xx][yy]=true;
		    	ans++;
		    	if (ans>=num) return true;
		    	q[++r][0]=xx;q[r][1]=yy;
		    }
    	}
    }
    return false;
}
long long work(int x,int y){
	long long l=0,r=inf,mid;
	while(l<r){
		mid=(l+r)/2;
		if (ok(x,y,mid,t)) r=mid;
		else l=mid+1;
	}
	return l;
}
int main(){
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	cin>>n>>m>>t;
	inf=0;
	int i,j,x;
	for(i=1;i<=n;++i)
	 for(j=1;j<=m;++j){
	 	scanf("%d",&a[i][j]);
	 	if (a[i][j]>inf) inf=a[i][j];
	 }
	long long ans=0;
	for(i=1;i<=n;++i)
	 for(j=1;j<=m;++j){
	 	scanf("%d",&x);
	 	if (x) ans+=work(i,j);
	 }
	cout<<ans<<endl;
}