結果

問題 No.519 アイドルユニット
コンテスト
ユーザー vjudge1
提出日時 2025-03-15 16:24:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,137 bytes
コンパイル時間 1,642 ms
コンパイル使用メモリ 160,148 KB
実行使用メモリ 59,704 KB
最終ジャッジ日時 2025-03-15 16:24:19
合計ジャッジ時間 6,253 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int N=2e7+5;
int dp[N],a[35][35],n,m=1,w[35],t[35],l[35];
int main()
{
	n=read();
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=read();
	for(int i=1;i<=n;i++)m*=2,l[i]=m/2;
	m--;
//	for(int i=1;i<=m;i++)dp[i]=2e9;
//	cout<<m<<'\n';
//	for(int i=1;i<=n;i++)
//	{
//		for(int j=i+1;j<=n;j++)dp[l[i]+l[j]]=a[i][j];
//	}
//		cout<<k<<'\n';
//	for(int i=1;i<=m;i++)cout<<dp[i]<<" ";cout<<'\n'<<'\n';
	for(int k=1;k<=m;k++)
	{
		int cnt=0;
		w[1]++;
		for(int i=1;i<=n;i++)
		{
			if(w[i]>1)
			{
				w[i]=0;
				w[i+1]++;
			}
			if(w[i]==1)t[++cnt]=i;
		}
		if(cnt%2==1)continue;
//		for(int i=1;i<=cnt;i++)cout<<t[i]<<' ';cout<<'\n';
		for(int i=1;i<=cnt;i++)
		{
			for(int j=i+1;j<=cnt;j++)
			{
//				cout<<k<<" "<<l[i]<<" "<<l[j]<<'\n';
				dp[k]=max(dp[k],dp[k-l[t[i]]-l[t[j]]]+a[t[i]][t[j]]);
			}
		}
//		cout<<k<<'\n';
//	for(int i=1;i<=m;i++)cout<<dp[i]<<" ";cout<<'\n'<<'\n';
	}
	cout<<dp[m];
	return 0;
}
0