MAUGIAO - The problem for kid
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<climits>
const int N = 20;
int f[1 << N], a[N][N], n;
long long c[1 << N];
void enter() {
scanf("%d", &n);
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
scanf("%d", &a[i][j]);
}
int snoob(const int &x) {
int r = x & -x, h = x + r;
return h | (x ^ h) / r >> 2;
}
void solve() {
const int Omega = 1 << n;
f[0] = 0; c[0] = 1;
for(int i = 0; i < n; ++i)
for(int s = (1 << (i+1)) - 1; s < Omega; s = snoob(s)) {
f[s] = INT_MIN;
for(int p = 0; p < n; ++p) if(s & 1 << p) {
const int ss = s & ~(1 << p);
if(f[ss] + a[i][p] > f[s]) {
f[s] = f[ss] + a[i][p];
c[s] = c[ss];
} else if(f[ss] + a[i][p] == f[s])
c[s] += c[ss];
}
}
printf("%d %lld\n", f[Omega - 1], c[Omega - 1]);
}
int main() {
enter();
solve();
return 0;
}