結果

問題 No.572 妖精の演奏
コンテスト
ユーザー chocorusk
提出日時 2018-12-11 23:47:15
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 6 ms / 2,000 ms
コード長 1,421 bytes
コンパイル時間 862 ms
コンパイル使用メモリ 97,016 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-24 17:35:31
合計ジャッジ時間 1,839 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘ll solve(ll, int, int, int)’:
main.cpp:33:58: warning: ‘i0’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   33 |         if(n==(1ll<<i0)) return memo[x][y][t]=dp[x][y][i0];
      |                                               ~~~~~~~~~~~^

ソースコード

diff # 

#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 <unordered_set>
#include <random>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
ll dp[31][31][34];
ll memo[31][31][34];
int m;
ll solve(ll n, int x, int y, int t){
	if(n==0) return 0;
	if(memo[x][y][t]) return memo[x][y][t];
	int i0;
	for(int i=33; i>=0; i--){
		if(n&(1ll<<i)){
			i0=i;
			break;
		}
	}
	if(n==(1ll<<i0)) return memo[x][y][t]=dp[x][y][i0];
	ll ans=0;
	for(int z=0; z<m; z++){
		ans=max(ans, dp[x][z][i0]+solve(n-(1ll<<i0), z, y, t+1));
	}
	return memo[x][y][t]=ans;
}
int main()
{
	ll n;
	cin>>n>>m;
	int a[30][30];
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<=33; k++){
				dp[i][j][k]=-1;
			}
		}
	}
	for(int i=0; i<m; i++){
		for(int j=0; j<m; j++){
			cin>>a[i][j];
			dp[i][j][0]=a[i][j];
		}
	}
	for(int i=0; i<33; i++){
		for(int j=0; j<m; j++){
			for(int k=0; k<m; k++){
				for(int l=0; l<m; l++){
				    if(dp[j][l][i]==-1 || dp[l][k][i]==-1) continue;
					dp[j][k][i+1]=max(dp[j][k][i+1], dp[j][l][i]+dp[l][k][i]);
				}
			}
		}
	}
	ll ans=0;
	for(int x=0; x<m; x++){
		for(int y=0; y<m; y++){
			ans=max(ans, solve(n-1, x, y, 0));
		}
	}
	cout<<ans<<endl;
	return 0;
}
0