Advertisement
Guest User

Untitled

a guest
Aug 21st, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.14 KB | None | 0 0
  1. #include <cmath>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int mat[16][16];
  9.  
  10. int main(void) {
  11. ios_base::sync_with_stdio(false);
  12. cin.tie(nullptr);
  13.  
  14. int tc;
  15. cin >> tc;
  16. for (int test_case = 1; test_case <= tc; test_case++) {
  17. int n;
  18. cin >> n;
  19. for (int i = 0; i < n; i++) {
  20. for (int j = 0; j < n; j++) {
  21. cin >> mat[i][j];
  22. }
  23. }
  24.  
  25. vector<int> idx(n, 1);
  26. for (int i = 0; i < n / 2; i++) {
  27. idx[i] = 0;
  28. }
  29.  
  30. int ans = -1;
  31. do {
  32. vector<int> food1, food2;
  33. for (int i = 0; i < n; i++) {
  34. if (idx[i] == 0) {
  35. food1.push_back(i);
  36. }
  37. else {
  38. food2.push_back(i);
  39. }
  40. }
  41. int sum1 = 0, sum2 = 0;
  42. for (int u = 0; u < food1.size(); u++) {
  43. for (int v = 0; v < food1.size(); v++) {
  44. sum1 += mat[food1[u]][food1[v]];
  45. }
  46. }
  47. for (int u = 0; u < food2.size(); u++) {
  48. for (int v = 0; v < food2.size(); v++) {
  49. sum2 += mat[food2[u]][food2[v]];
  50. }
  51. }
  52.  
  53. int diff = abs(sum1 - sum2);
  54. if (ans == -1 || ans > diff) {
  55. ans = diff;
  56. }
  57.  
  58. } while (next_permutation(idx.begin(), idx.end()));
  59.  
  60. cout << "#" << test_case << " " << ans << '\n';
  61. }
  62.  
  63. return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement