PROG-1038: Bond

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
const double INF = 1e9;

int n,Bit;
double ar[30][30];
vector <double> dp(1048575,-INF);

double bond(int bit,int i){
    if(bit == Bit) return 1.0;
    if(dp[bit] != -INF) return dp[bit];
    for(int j=0; j<n; j++){
        if(bit & (1<<j)) continue;
        dp[bit] = max(dp[bit], ar[i][j] * bond(bit | 1<<j,i+1) );
    }
    return dp[bit];
}

int main(){

    scanf("%d",&n);

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            int x;
            scanf("%d",&x);
            ar[i][j] = (double)x/100.0;
        }
    }

    Bit = (1<<n) - 1;
    printf("%.6f",bond(0,0)*100);

    return 0;
}