結果

問題 No.519 アイドルユニット
ユーザー vjudge1
提出日時 2025-03-15 16:21:58
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,203 bytes
コンパイル時間 1,659 ms
コンパイル使用メモリ 162,024 KB
実行使用メモリ 17,848 KB
最終ジャッジ日時 2025-03-15 16:22:04
合計ジャッジ時間 6,251 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other TLE * 1 -- * 33
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:14:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         freopen("group.in","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
main.cpp:15:16: warning: ignoring return value of ‘FILE* freopen(const char*, const char*, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   15 |         freopen("group.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

ソースコード

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=1<<25;
int dp[N],a[35][35],n,m=1,w[35],t[35],l[35];
int main()
{
	freopen("group.in","r",stdin);
	freopen("group.out","w",stdout);
	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