Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <map>
- using namespace std;
- int n, answerr = 0;
- vector<vector<int>> g;
- vector<int> ans1, ans2;
- void find(int cur, vector<int> a1, vector<int> a2) {
- if (cur == n) {
- if (a1.empty() || a2.empty()) {
- return;
- }
- int sum = 0;
- for (int i : a1) {
- for (int j : a2) {
- sum += g[i][j];
- }
- }
- if (answerr < sum) {
- answerr = sum;
- ans1 = a1;
- ans2 = a2;
- }
- return;
- }
- a1.push_back(cur);
- find(cur + 1, a1, a2);
- a1.pop_back();
- a2.push_back(cur);
- find(cur + 1, a1, a2);
- a2.pop_back();
- }
- void input() {
- cin >> n;
- vector<int> a(n);
- g.resize(n + 1, vector<int>(n + 1));
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < n; ++j) {
- cin >> g[i][j];
- }
- }
- }
- void output() {
- cout << answerr << endl;
- vector<int> answer(n);
- for (int i : ans1) {
- answer[i] = 1;
- }
- for (int i : ans2) {
- answer[i] = 2;
- }
- for (int i : answer) {
- cout << i << " ";
- }
- }
- void solve() {
- input();
- find(0, {}, {});
- output();
- }
- int main() {
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement