fork download 
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 1234
  13. #define MAX 1037471823
  14.  
  15. using namespace std;
  16.  
  17. struct node
  18. {
  19. 	int x, y;
  20. 	bool operator < (const node &k) const { return y < k.y; }
  21. } a;
  22. struct node2
  23. {
  24. 	int x, y;
  25. 	bool operator < (const node2 &k) const { return y > k.y; }
  26. } a2;
  27. int n, m, k, w[MS][MS], dmin[MS][MS], dmax[MS][MS], rmin[MS][MS], rmax[MS][MS], ans;
  28.  
  29. int main()
  30. {
  31. 	scanf("%d%d%d", &n, &m, &k);
  32. 	rep(i, 1, n) rep(j, 1, m) scanf("%d", &w[i][j]);
  33. 	rep(j, 1, m) rep(i, 1, n-k+1) dmin[i][j] = MAX, dmax[i][j] = -MAX; 
  34. 	rep(j, 1, m) 
  35. 	{
  36. 		priority_queue <node> q;
  37. 		rep(i, 1, k) { a.x = i; a.y = w[i][j]; q.push(a); }
  38. 		dmax[1][j] = q.top().y;
  39. 		rep(i, 2, n-k+1)
  40. 		{
  41. 			while (q.top().x < i) q.pop();
  42. 			a.x = i+k-1, a.y = w[i+k-1][j]; q.push(a);
  43. 			dmax[i][j] = q.top().y;
  44. 		}
  45. 	}
  46. 	rep(j, 1, m) 
  47. 	{
  48. 		priority_queue <node2> q;
  49. 		rep(i, 1, k) { a2.x = i; a2.y = w[i][j]; q.push(a2); }
  50. 		dmin[1][j] = q.top().y;
  51. 		rep(i, 2, n-k+1)
  52. 		{
  53. 			while (q.top().x < i) q.pop();
  54. 			a2.x = i+k-1, a2.y = w[i+k-1][j]; q.push(a2);
  55. 			dmin[i][j] = q.top().y;
  56. 		}
  57. 	}
  58. 	rep(i, 1, n-k+1) 
  59. 	{
  60. 		priority_queue <node> q;
  61. 		rep(j, 1, k) { a.x = j; a.y = dmax[i][j]; q.push(a); }
  62. 		rmax[i][1] = q.top().y;
  63. 		rep(j, 2, m-k+1)
  64. 		{
  65. 			while (q.top().x < j) q.pop();
  66. 			a.x = j+k-1, a.y = dmax[i][j+k-1]; q.push(a);
  67. 			rmax[i][j] = q.top().y;
  68. 		}
  69. 	}
  70. 	rep(i, 1, n-k+1) 
  71. 	{
  72. 		priority_queue <node2> q;
  73. 		rep(j, 1, k) { a2.x = j; a2.y = dmin[i][j]; q.push(a2); }
  74. 		rmin[i][1] = q.top().y;
  75. 		rep(j, 2, m-k+1)
  76. 		{
  77. 			while (q.top().x < j) q.pop();
  78. 			a2.x = j+k-1, a2.y = dmin[i][j+k-1]; q.push(a2);
  79. 			rmin[i][j] = q.top().y;
  80. 		}
  81. 	}
  82. 	ans = MAX;
  83. 	rep(i, 1, n-k+1) rep(j, 1, m-k+1) if (ans > rmax[i][j] - rmin[i][j]) ans = rmax[i][j] - rmin[i][j];
  84. 	printf("%d\n", ans);
  85. 	return 0;
  86. }
Success #stdin #stdout 0s 33224KB
comments (?)
stdin 
5 4 2
1 2 5 6
0 17 16 0
16 17 2 1
2 10 2 1
1 2 2 2
stdout 
1
https://ideone.com/NuNUPs
BZOJ 1047
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!