fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef double lf;
  5. typedef long long ll;
  6. typedef long double LF;
  7. typedef unsigned long long ull;
  8. typedef set<ll> sll;
  9. typedef vector<ll> vll;
  10. typedef map<string,ll> msl;
  11. typedef pair<ll,ll> pll;
  12. typedef vector<pll > vpll;
  13. typedef map<ll,ll> mll;
  14.  
  15. #define gc getchar
  16. #define lp(i,a,b) for(ll i = ll(a); i<ll(b) ; i++) 
  17. #define itvll(c,it) for(vll::iterator it = c.begin() ; it!=c.end() ; it++)
  18. #define itmll(c,it) for(mll::iterator it = c.begin() ; it!=c.end() ; it++)
  19. #define itmsl(c,it) for(msl::iterator it = c.begin() ; it!=c.end() ; it++)
  20.  
  21. ll ip(){
  22. 	ll x = 0; bool isNeg = false; char c;
  23. 	c = gc();
  24. 	if(c == '-')	isNeg = true , c = gc();
  25. 	for( ; c >= '0'  && c <= '9' ; c = gc() )	x = (x << 1) + (x << 3) + c - '0';
  26. 	if(isNeg)	x *= -1;	return x;
  27. }
  28.  
  29. ll binarySearch(vector<ll> &arr){
  30. 	ll sz = arr.size();
  31. 	lp(i,1,sz-1){
  32. 		if(arr[i+1] > arr[i] && arr[i]==arr[i-1]){
  33. 			return arr[i];
  34. 		}
  35. 	}
  36. }
  37.  
  38. int main(){
  39. 	ios::sync_with_stdio(false);
  40. 	cin.tie(NULL);
  41. 	ll t,n,m;
  42. 	t = ip();
  43. 	while(t--){          
  44. 		n = ip() ; m = ip();
  45. 		ll c[n][m];          
  46. 		ll x;
  47.  
  48. 		lp(p,0,2){
  49. 			lp(i,0,n){
  50. 				lp(j,0,m){
  51. 					x = ip();
  52. 					if(p)	c[i][j] -= x;
  53. 					else c[i][j] = x;
  54. 				}
  55. 			}		
  56. 		}
  57.  
  58. 		bool flag = true;
  59. 		lp(i,0,n){
  60. 			lp(j,0,m){
  61. 				if(c[i][j] + c[0][0] != c[i][0] + c[0][j]){
  62. 					flag = false;
  63. 					break;
  64. 				}
  65. 				if(!flag)	break;
  66. 			}
  67. 		}
  68. 		if(!flag){
  69. 			cout << -1 << "\n";
  70. 			continue;
  71. 		}
  72. 		// if program reaches here , then optimal solution exists
  73. 		vector<ll> arr;
  74. 		lp(i,0,n)	arr.push_back( -c[0][0] + c[i][0] );
  75. 		lp(j,0,m)	arr.push_back( -c[0][j] );
  76. 		sort(arr.begin(),arr.end());              
  77. 		//ll median = arr[(n+m)/2];
  78. 		ll ans = 0;
  79. 		ll k = binarySearch(arr);
  80. 		lp(i,0,n+m)	ans += abs(arr[i]-k);	
  81. 		cout << ans << "\n";	
  82. 	}
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 3472KB
comments (?)
stdin
copy 
3
2 2
1 1
1 1
1 2
3 4
2 2
1 9
9 1
9 1
1 9
1 4
4 5 7 1
2 3 4 5
stdout
copy 
3
-1
9
https://ideone.com/qFtK2x
language:
C++14 (gcc 8.3)
created:
7 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!