fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define endl '\n'
  4. #define left jhghajkhja
  5. #define right oauighgajk
  6. #define prev aioghajga
  7. #define next ioyhjhfajasj
  8. #define y0 iuadoghasdgj
  9. #define y1 taklahgjkla
  10. #define remainder pogjuakllhga
  11. #define pow pajklgaklha
  12. #define pow10 iopuioadjlgkah
  13. #define div aljghajkghak
  14. #define distance gkuftgjasgfjh
  15. #define uppercase ifyhasjkhakjfas
  16. #define count sajhfkajfa
  17. #define rank asfhujfasj
  18.  
  19. //#define floor hjakjhaja
  20. //#define time ashjlahjka
  21. //#define double_t double
  22. //#define tm kahjflahaajk
  23.  
  24. using namespace std;
  25.  
  26. const int N = 1024;
  27. const int INF = (1e9) + 7;
  28.  
  29. int n,m,a[N][N],arr[N*N],sz,ptr[N],ans;
  30. struct cmp {
  31. 	bool operator ()(const int &x, const int &y) const {
  32. 		return a[x][ptr[x]]>a[y][ptr[y]];
  33. 	}
  34. };
  35. priority_queue < int, vector < int >, cmp > q;
  36. int curr,max_value;
  37.  
  38. int main() {
  39. 	ios_base::sync_with_stdio(false);
  40. 	cin.tie(NULL);
  41. 	//freopen("test.txt","r",stdin);
  42. 	//freopen(IN.c_str(),"r",stdin);
  43. 	//freopen(OUT.c_str(),"w",stdout);
  44. 	int i,j;
  45.  
  46. 	scanf("%d %d", &n, &m);
  47. 	for(i=1;i<=n;i++) {
  48. 		for(j=1;j<=m;j++) {
  49. 			scanf("%d", &a[i][j]);
  50. 			arr[++sz]=a[i][j];
  51. 		}
  52. 		ptr[i]=1;
  53. 		sort(a[i]+1,a[i]+1+m);
  54. 		a[i][m+1]=INF;
  55. 		q.push(i);
  56. 		max_value=max(max_value,a[i][ptr[i]]);
  57. 	}
  58. 	sort(arr+1,arr+1+sz);
  59. 	ans=INF;
  60. 	for(i=1;i<=sz;i++) {
  61. 		if(max_value>arr[i]) continue;
  62. 		while(true) {
  63. 			curr=q.top();
  64. 			if(a[curr][ptr[curr]+1]>arr[i]) break;
  65. 			q.pop();
  66. 			++ptr[curr];
  67. 			max_value=max(max_value,a[curr][ptr[curr]]);
  68. 			q.push(curr);
  69. 		}
  70. 		ans=min(ans,arr[i]-a[q.top()][ptr[q.top()]]);
  71. 	}
  72. 	printf("%d\n", ans);
  73.  
  74. 	//fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
  75.  
  76. 	return 0;
  77. }
  78.  
Success #stdin #stdout 0s 11664KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000007
https://ideone.com/BEm6BL
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!