georgiy110802

Untitled

Jun 13th, 2021
570
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int n, minr = 0;
  6. vector<vector<int>> g;
  7. vector<int> ans1, ans2;
  8.  
  9. void find(int cur, vector<int> a1, vector<int> a2) {
  10.     if (cur == n) {
  11.         if (a1.empty() || a2.empty()) {
  12.             return;
  13.         }
  14. //        for (int i : a1)
  15. //            cout << i << " ";
  16. //        cout << "\n";
  17. //        for (int i : a2)
  18. //            cout << i << " ";
  19. //        cout << "\n\n";
  20.         int sum = 0;
  21.         for (int i = 0; i < a1.size(); ++i) {
  22.             for (int j = 0; j < a2.size(); ++j) {
  23.                 sum += g[a1[i]][a2[j]];
  24.             }
  25.         }
  26.         if (minr < sum) {
  27.             minr = sum;
  28.             ans1 = a1;
  29.             ans2 = a2;
  30.         }
  31.         return;
  32.     }
  33.     a1.push_back(cur);
  34.     find(cur + 1, a1, a2);
  35.     a1.pop_back();
  36.     a2.push_back(cur);
  37.     find(cur + 1, a1, a2);
  38.     a2.pop_back();
  39. }
  40.  
  41. main() {
  42.     cin >> n;
  43.     vector<int> a(n);
  44.     g.resize(n + 1, vector<int>(n + 1));
  45.     for (int i = 0; i < n; ++i) {
  46.         for (int j = 0; j < n; ++j) {
  47.             cin >> g[i][j];
  48.         }
  49.     }
  50.     find(0, {}, {});
  51.     cout << minr << "\n";
  52.     vector<int> answer(n);
  53.     for (int i : ans1) {
  54.         answer[i] = 1;
  55.     }
  56.     for (int i : ans2) {
  57.         answer[i] = 2;
  58.     }
  59.     for (int i : answer) {
  60.         cout << i << " ";
  61.     }
  62.  
  63. }
RAW Paste Data