この問題は 山登り法 を使って解くことができます。 (以下の解説は山登り法を知らなくても読むことができます。)

\(X, Y\) をそれぞれ 部屋 X,Y にいる人の集合と定義します。 また、部屋の割り当て \((X,Y)\) に対するスコア \(f(X,Y)\) を以下のように定義します。

\(f(X,Y) = \sum_{i,j ∈ X} A_{ij} + \sum_{i,j ∈ Y} A_{ij}\)

直感的に考えると、スコアが高いほど、良い状態である人が多そうです。ここで、スコアの改善を考えます。

良い状態でない人を一人選び、部屋を移動すると、スコアは \(1\) 以上増えます。この操作を行える限り繰り返します。操作が行えなくなったときはつまり、\(N\) 人全員が良い状態であるときです。よって、操作が行えなくなった時点でその時の状態を出力すれば良いです。スコアには上限があるため、操作は有限回で終了します。

スコアの範囲は広く見積もっても \(\pm \sum |A_{i,j}|\) 程度です。操作のたびに差分更新を行えば、各操作を \(O(N)\) で行えるため、全体の計算量は \(O(N^3 \max A)\) です。
更新に \(O(N^2)\) かけて \(O(N^4 \max A)\) で解いても良いです。