MAUGIAO - The problem for kid
Tác giả: RR
Ngôn ngữ: C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>
#define FOR(i,a,b) for(i = a; i <= b; ++i)
#define REP(i,a) for(i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
using namespace std;
#define TWO(x) (1<<(x))
#define CONTAIN(S,x) (S & TWO(x))
;
int f[1100111], n, a[22][22];
long long g[1100111];
vector<int> ls[22];
int main() {
int i, mask, j;
scanf("%d", &n); FOR(i,1,n) FOR(j,1,n) scanf("%d", &a[i][j]);
f[0] = 0;
g[0] = 1;
int cnt;
REP(mask,TWO(n)) {
cnt = 0;
REP(i,n)
if (CONTAIN(mask,i)) ++cnt;
ls[cnt].PB(mask);
}
int cur, mask2, x, sz;
FOR(i,0,n-1) {
sz = ls[i].size();
REP(x,sz) {
mask = ls[i][x];
if (!*(g+mask)) continue;
REP(j,n) if (!CONTAIN(mask,j)) {
cur = *(f+mask) + a[i+1][j+1];
mask2 = mask + TWO(j);
if (cur > *(f+mask2)) {
*(f+mask2) = cur;
*(g+mask2) = *(g+mask);
}
else if (cur == *(f+mask2))
*(g+mask2) += *(g+mask);
}
}
}
cout << f[TWO(n)-1] << ' ' << g[TWO(n)-1] << endl;
return 0;
}