CodeStar2023年春第3周周赛普及进阶组

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    int m = 2*n;
    vector<vector<int>> a(m, vector<int>(m));
    rep(i, m)rep(j, m) cin >> a[i][j];
	
	ll ans = -1e18;
	vector<int> matched(m);
	auto dfs = [&](auto& f, int step, int cnt, ll now) -> void {
    	if (cnt == n) {
    	    ans = max(ans, now);
    	    return;
    	}
    	
    	if (matched[step]) {
    	    f(f, step+1, cnt, now);
    	    return;
    	} 
    	for (int i = step+1; i < m; ++i) {
    	    // 1. 剪枝
    	    if (matched[i]) continue;
    	    // 2. 试探
    	    matched[i] = matched[step] = true;
    	    f(f, step+1, cnt+1, now*a[step][i]);
    	    // 3. 回溯
    	    matched[i] = matched[step] = false;
    	}
	};
	
	dfs(dfs, 0, 0, 1);
	
	cout << ans << '\n';
    
    return 0;
}