fork download
copy 
  1. // iostream is too mainstream
  2. #include <cstdio>
  3. // bitch please
  4. #include <iostream>
  5. #include <vector>
  6. #include <set>
  7. #include <map>
  8. #include <string>
  9. #include <queue>
  10. #include <stack>
  11. #include <algorithm>
  12. #include <cmath>
  13. #include <iomanip>
  14. #define dibs reserve
  15. #define OVER9000 1234567890
  16. #define patkan 9
  17. #define tisic 47
  18. #define soclose 1e-9
  19. #define pi 3.1415926535898
  20. #define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
  21. #define chocolate win
  22. #define ff first
  23. #define ss second
  24. #define abs(x) ((x < 0)?-(x):(x))
  25. #define uint unsigned int
  26. // mylittlepony
  27. using namespace std;
  28.  
  29. struct infoE {
  30. 	int a,b,d;
  31.  
  32. 	bool operator<(const infoE &E) const {
  33. 		return d < E.d;}
  34. 	};
  35.  
  36. int main() {
  37. //	freopen("skilevel.in","r",stdin);
  38. //	freopen("skilevel.out","w",stdout);
  39. 	int N,M,T;
  40. 	scanf(" %d %d %d",&N,&M,&T);
  41. 	vector< vector<int> > H(N, vector<int>(M));
  42. 	for(int i =0; i < N*M; i++) scanf(" %d",&H[i/M][i%M]);
  43.  
  44. 	vector<infoE> E;
  45. 	vector<int> D(N*M);
  46. 	int dx[] ={1,-1,0,0};
  47. 	int dy[] ={0,0,1,-1};
  48. 	for(int i =0; i < N*M; i++) for(int k =0; k < 4; k++) {
  49. 		int x =i/M+dx[k], y =i%M+dy[k];
  50. 		if(x < 0 || y < 0 || x >= N || y >= M) continue;
  51. 		infoE I;
  52. 		I.a =x*M+y;
  53. 		I.b =i;
  54. 		I.d =abs(H[i/M][i%M]-H[x][y]);
  55. 		E.push_back(I);}
  56. 	sort(E.begin(),E.end());
  57.  
  58. 	vector< vector<int> > C(N*M);
  59. 	vector<int> isC(N*M);
  60. 	for(int i =0; i < N*M; i++) {
  61. 		C[i].resize(1,i);
  62. 		isC[i] =i;}
  63.  
  64. 	for(uint e =0; e < E.size(); e++) {
  65. 		int x =E[e].a, y =E[e].b;
  66. 		if(isC[x] == isC[y]) continue;
  67. 		x =isC[x], y =isC[y];
  68. 		if(C[x].size() < C[y].size()) swap(x,y);
  69. 		// y do x
  70. 		if((int)(C[x].size()+C[y].size()) >= T) {
  71. 			if((int)C[x].size() < T)
  72. 				for(uint j =0; j < C[x].size(); j++) D[C[x][j]] =E[e].d;
  73. 			if((int)C[y].size() < T)
  74. 				for(uint j =0; j < C[y].size(); j++) D[C[y][j]] =E[e].d;
  75. 			}
  76. 		for(uint j =0; j < C[y].size(); j++) {
  77. 			isC[C[y][j]] =x;
  78. 			C[x].push_back(C[y][j]);}
  79. 		}
  80.  
  81. 	long long ans =0;
  82. 	for(int i =0; i < N*M; i++) {
  83. 		int a;
  84. 		scanf(" %d",&a);
  85. 		ans +=a*(long long)(D[i]);}
  86. 	printf("%lld\n",ans);
  87. 	return 0;}
  88.  
  89. // look at my code
  90. // my code is amazing
  91.  
Runtime error #stdin #stdout #stderr 0s 3436KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/UoDQx9
usaco jan14 gold3
language:
C++14 (gcc 8.3)
created:
10 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!