結果

問題 No.753 最強王者決定戦
コンテスト
ユーザー chocorusk
提出日時 2018-11-10 10:59:16
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 622 ms / 1,000 ms
コード長 1,390 bytes
コンパイル時間 893 ms
コンパイル使用メモリ 97,760 KB
実行使用メモリ 11,648 KB
最終ジャッジ日時 2024-11-23 15:25:59
合計ジャッジ時間 4,234 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
int main()
{
	int a[16][16];
	for(int i=0; i<16; i++){
		for(int j=0; j<16; j++){
			cin>>a[i][j];
		}
	}
	ll dp[16][1<<16]={};
	for(int i=0; i<16; i++){
		for(int j=0; j<i; j++){
			if(a[j][i]>0) dp[j][(1<<i)+(1<<j)]=2;
			else dp[i][(1<<i)+(1<<j)]=2;
		}
	}
	for(int k=2; k<=4; k++){
		for(int i=0; i<(1<<16); i++){
			int c=0;
			for(int j=0; j<16; j++){
				if(i&(1<<j)) c++;
			}
			if(c!=(1<<k)) continue;
			for(int j=i; j>0; j=(j-1)&i){
				int c=0;
				for(int l=0; l<16; l++){
					if(j&(1<<l)) c++;
				}
				if(c!=(1<<(k-1))) continue;
				vector<int> v1, v2;
				for(int l=0; l<16; l++){
					if(j&(1<<l)) v1.push_back(l);
					else v2.push_back(l);
				}
				for(auto x:v1){
					for(auto y:v2){
						if(x<y){
							if(a[x][y]>0) dp[x][i]+=(dp[x][j]*dp[y][i-j]);
							else dp[y][i]+=(dp[x][j]*dp[y][i-j]);
						}else{
							if(a[y][x]>0) dp[y][i]+=(dp[x][j]*dp[y][i-j]);
							else dp[x][i]+=(dp[x][j]*dp[y][i-j]);
						}
					}
				}
			}
		}
	}
	for(int i=0; i<16; i++){
		cout<<dp[i][(1<<16)-1]<<endl;
	}
	return 0;
}
0