比赛 |
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);
}