georgiy110802

Untitled

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