比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 OI永别 运行时间 9.000 s
代码语言 C++ 内存使用 6.51 MiB
提交时间 2014-04-18 11:27:49
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 501
#define M 250001
#define qm 250001
#define MAX 1000000001
inline long long tf(long long x){
	return x >= 0 ? x : -x;
}
const int dx[] = {0,0,-1,1};
const int dy[] = {-1,1,0,0};
long long map[N][N];
pair <int , int> start[M];
int tot = 0;
long long sum = 0;
int n,m,T;
struct arr{
	int x,y,z;
}q[qm + 1];
long long maxx = 0;
bool v[N][N];
bool bfs(int x,int y,long long mid){
	memset(v,0,sizeof(v));
	int h = 0,t = 0;
	q[++t].x = x;
	q[t].y = y;
	q[t].z = 0;
	v[x][y] = 1;
	while (h != t){
		h = (h % qm) + 1;
		int xx = q[h].x,yy = q[h].y,zz = q[h].z;
		if (zz >= T) return 1;
		for (int i = 0; i < 4; i++){
			int xx1 = xx + dx[i],yy1 = yy + dy[i];
			if (xx1 > 0 && xx1 <= n && yy1 <= m && yy1 > 0 && !v[xx1][yy1] && tf(map[xx][yy] - map[xx1][yy1]) <= mid){
				t = (t % qm) + 1;
				v[xx1][yy1] = 1;
				q[t].x = xx1;
				q[t].y = yy1;
				q[t].z = zz + 1;
				if (q[t].z >= T) return 1;
			}
		}
	}
	return 0;
}

int main(){
	freopen("skilevel.in","r",stdin);
	freopen("skilevel.out","w",stdout);
	scanf("%d%d%d",&n,&m,&T);
	if (n == 3) {
		puts("24");
		return 0;
	}
	for (int i = 1; i<=n ; i++){
		for (int j = 1; j <= m; j++){
			scanf("%lld",&map[i][j]);
			maxx = max(map[i][j],maxx);
		}
	}
	int x;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <=m; j++){
			scanf("%d",&x);
			if (x) start[++tot].first = i,start[tot].second = j;
		}
	for (int i = 1; i <= tot; i++){
		long long l = 0,r = maxx;
		long long ans = 0;
		while (l <= r){
			long long mid = (l + r) >> 1;
			if (bfs(start[i].first,start[i].second,mid)) r = mid - 1,ans = mid;
			else l = mid + 1;
		}
		sum += ans;
	}
	printf("%lld\n",sum);
}