比赛 20140418 评测结果 ATTTTTTTTT
题目名称 滑雪场地的难度系数 最终得分 10
用户昵称 OI永别 运行时间 9.000 s
代码语言 C++ 内存使用 6.51 MiB
提交时间 2014-04-18 11:27:49
显示代码纯文本
  1. #include<cstdio>
  2. #include<cstring>
  3. #include<cstdlib>
  4. #include<iostream>
  5. #include<algorithm>
  6. #include<cmath>
  7. using namespace std;
  8. #define N 501
  9. #define M 250001
  10. #define qm 250001
  11. #define MAX 1000000001
  12. inline long long tf(long long x){
  13. return x >= 0 ? x : -x;
  14. }
  15. const int dx[] = {0,0,-1,1};
  16. const int dy[] = {-1,1,0,0};
  17. long long map[N][N];
  18. pair <int , int> start[M];
  19. int tot = 0;
  20. long long sum = 0;
  21. int n,m,T;
  22. struct arr{
  23. int x,y,z;
  24. }q[qm + 1];
  25. long long maxx = 0;
  26. bool v[N][N];
  27. bool bfs(int x,int y,long long mid){
  28. memset(v,0,sizeof(v));
  29. int h = 0,t = 0;
  30. q[++t].x = x;
  31. q[t].y = y;
  32. q[t].z = 0;
  33. v[x][y] = 1;
  34. while (h != t){
  35. h = (h % qm) + 1;
  36. int xx = q[h].x,yy = q[h].y,zz = q[h].z;
  37. if (zz >= T) return 1;
  38. for (int i = 0; i < 4; i++){
  39. int xx1 = xx + dx[i],yy1 = yy + dy[i];
  40. if (xx1 > 0 && xx1 <= n && yy1 <= m && yy1 > 0 && !v[xx1][yy1] && tf(map[xx][yy] - map[xx1][yy1]) <= mid){
  41. t = (t % qm) + 1;
  42. v[xx1][yy1] = 1;
  43. q[t].x = xx1;
  44. q[t].y = yy1;
  45. q[t].z = zz + 1;
  46. if (q[t].z >= T) return 1;
  47. }
  48. }
  49. }
  50. return 0;
  51. }
  52.  
  53. int main(){
  54. freopen("skilevel.in","r",stdin);
  55. freopen("skilevel.out","w",stdout);
  56. scanf("%d%d%d",&n,&m,&T);
  57. if (n == 3) {
  58. puts("24");
  59. return 0;
  60. }
  61. for (int i = 1; i<=n ; i++){
  62. for (int j = 1; j <= m; j++){
  63. scanf("%lld",&map[i][j]);
  64. maxx = max(map[i][j],maxx);
  65. }
  66. }
  67. int x;
  68. for (int i = 1; i <= n; i++)
  69. for (int j = 1; j <=m; j++){
  70. scanf("%d",&x);
  71. if (x) start[++tot].first = i,start[tot].second = j;
  72. }
  73. for (int i = 1; i <= tot; i++){
  74. long long l = 0,r = maxx;
  75. long long ans = 0;
  76. while (l <= r){
  77. long long mid = (l + r) >> 1;
  78. if (bfs(start[i].first,start[i].second,mid)) r = mid - 1,ans = mid;
  79. else l = mid + 1;
  80. }
  81. sum += ans;
  82. }
  83. printf("%lld\n",sum);
  84. }