\(2N\) 人の参加者が \(N\) 個のペアに分かれる方法（以下、単に「分け方」と呼ぶ）をすべて全探索し、その中での舞踏会全体の楽しさの最大値を出力すれば良いです。
以下では、分け方の個数が最大となる \(N = 8\) の場合を例に説明します。

分け方を \(1\) つ選ぶ自然な方法として、次のような手順を考えます。

• \(1\) 個目のペアの \(1\) 人目を誰にするかを、\(16\) 人の中から選ぶ。
• \(1\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(15\) 人の中から選ぶ。
• \(2\) 個目のペアの \(1\) 人目を誰にするかを、残りの \(14\) 人の中から選ぶ。
• \(2\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(13\) 人の中から選ぶ。
• \(3\) 個目のペアの \(1\) 人目を誰にするかを、残りの \(12\) 人の中から選ぶ。
• \(3\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(11\) 人の中から選ぶ。
• \(\cdots\)
• \(8\) 個目のペアの \(1\) 人目を誰にするかを、残りの \(2\) 人の中から選ぶ。
• \(8\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(1\) 人の中から選ぶ。

この方法ですべての分け方を全探索すると、\(16 \times 15 \times 14 \times \cdots \times 2 \times 1 > 2 \times 10^{13}\) 通りの選び方を探索することになり、実行制限時間に間に合わせることはできません。

上記の探索方法では、同じ分け方を複数回探索することになり、冗長です。

例えば、\(i\) 個目のペアの \(1 \)人目を \(x_{i, 1}\) 、\(2\) 人目を \(x_{i, 2}\) で表すと、上記の探索方法では次の \(3\) つの選び方はそれぞれ異なる選び方として調べられますが、これらは実際には本質的に同じ分け方です。

• \(\big((x_{1, 1}, x_{1, 2}), (x_{2, 1}, x_{2, 2}), \ldots, (x_{8, 1}, x_{8, 2})\big) = \big((1, 2), (3, 4), \ldots, (15, 16)\big)\)

• \(\big((x_{1, 1}, x_{1, 2}), (x_{2, 1}, x_{2, 2}), \ldots, (x_{8, 1}, x_{8, 2})\big) = \big((2, 1), (4, 3), \ldots, (16, 15)\big)\)

• \(\big((x_{1, 1}, x_{1, 2}), (x_{2, 1}, x_{2, 2}), \ldots, (x_{8, 1}, x_{8, 2})\big) = \big((15, 16), (13, 14), \ldots, (1, 2)\big)\)

これへの対処として、上記の探索法を「各ペアの \(1\) 人目はその時点で残っている人の中で番号が最小の参加者とする」ように改良します。 すなわち、次のような方法を考えます。

• \(1\) 個目のペアの \(1\) 人目を、\(16\) 人の中で番号が最小の参加者（つまり人 \(1\) ）とする。
• \(1\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(15\) 人の中から選ぶ。
• \(2\) 個目のペアの \(1\) 人目を、残りの \(14\) 人の中で番号が最小の参加者とする。
• \(2\)個目のペアの \(2\) 人目を誰にするかを、残りの \(13\) 人の中から選ぶ。
• \(3\) 個目のペアの \(1\) 人目を、残りの \(12\) 人の中で番号が最小の参加者とする。
• \(3\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(11\) 人の中から選ぶ。
• \(\cdots\)
• \(8\) 個目のペアの \(1\) 人目を、残りの \(2\) 人の中で番号が最小の参加者とする。
• \(8\) 個目のペアの \(2\) 人目を誰にするかを、残りの \(1\) 人の中から選ぶ。

この方法ですべての分け方を全探索すると、各ペアの \(1\) 人目は随時 \(1\) 通りに定まるため、\(15 \times 13 \times 11 \times 9 \times 7 \times 5 \times 3 \times 1 =2027025\) 通りの選び方を探索すればよく、実行制限時間に間に合わせることができます。

C++言語による正解例を以下に記載します。

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int n;
int a[20][20];

vector<pair<int, int>> vec;
bool used[20];

int calc()
{
  if(vec.size() == n){
    int ret = 0;
    for(auto p : vec) ret ^= (a[p.first][p.second]);
    return ret;
  }
  
  int l;
  for(int i = 1; i <= 2*n; i++){
    if(!used[i]){
      l = i;
      break;
    }
  }
  used[l] = true;

  int ret = 0;
  for(int i = 1; i <= 2*n; i++){
    if(!used[i]){
      vec.push_back({l, i}), used[i] = true;
      ret = max(ret, calc());
      vec.pop_back(), used[i] = false;
    }
  }
    
  used[l] = false;
  return ret;
}

int main(void)
{
  cin >> n;
  for(int i = 1; i <= 2*n-1; i++){
    for(int j = i+1; j <= 2*n; j++){
      cin >> a[i][j];
    }
  }
  cout << calc() << endl;

  return 0;
}