結果

問題 No.1598 4×4 Grid
コンテスト
ユーザー aogera
提出日時 2025-12-28 18:15:01
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 240 ms / 4,000 ms
コード長 877 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,982 ms
コンパイル使用メモリ 349,504 KB
実行使用メモリ 116,864 KB
最終ジャッジ日時 2025-12-28 18:15:09
合計ジャッジ時間 7,384 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<bits/extc++.h>
using namespace std;
using ll=long long;

int main(){
	ll K;cin>>K;
	const int N=16;
	const int MK=217;
	vector aja(N,vector(N,false));
	for(int i=0;i<4;i++) for(int j=0;j<3;j++){
		aja[i*4+j][i*4+j+1]=1;
		aja[i*4+j+1][i*4+j]=1;
	}
	for(int i=0;i<3;i++) for(int j=0;j<4;j++){
		aja[i*4+j][i*4+j+4]=1;
		aja[i*4+j+4][i*4+j]=1;
	}

	vector<ll> br(1<<N);
	for(ll msk=0;msk<(1<<N);msk++){
		ll cnt=0;
		for(int x=0;x<N;x++) if(msk>>x&1){
			for(int y=0;y<N;y++) if(!(msk>>y&1)){
				if(aja[x][y])cnt++;
			}
		}		
		br[msk]=cnt;
	}


	vector dp(1<<N,vector(MK,0LL));
	dp[0][0]=1;
	for(ll msk=0;msk<(1<<N)-1;msk++){
		for(ll k=0;k<MK;k++){
			if(dp[msk][k]==0) continue;

			ll m=popcount(unsigned(msk))+1;
			for(int i=0;i<N;i++) if(!(msk>>i&1)){
				ll nmsk=msk|(1LL<<i);
				dp[nmsk][k+br[nmsk]]+=dp[msk][k];
			}
		}
	}

	cout<<dp[(1<<N)-1][K]<<endl;

}
0