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