Submission

[PPPPPPPPPPPPPPP]

Score: 100

User: njoop

Problemset: forex

Language: cpp

Time: 0.008 second

Submitted On: 2025-04-04 02:26:13

#include<bits/stdc++.h>
#define pii pair<int,int>
#define d long double
using namespace std;

const int N = 30;

d a[N+5][N+5];
d dp[N+5][N+5];
int main(){
	int n, idx=0, mn = 1e9;
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	for(int x=1;x<=n;x++){
		vector<vector<d>> dp(n+1,vector<d>(n+5,0));
		dp[x][0] = 1.00;
		for(int k=1;k<=n;k++){
			for(int y=1;y<=n;y++){
				if(dp[y][k-1] == 0) continue;
				for(int z=1;z<=n;z++){
					dp[z][k] = max(dp[z][k],dp[y][k-1]*a[y][z]);
				}
				if(dp[x][k] > 1.01 && k < mn){
					idx = x;
					mn = k;
				}
			}
		}
	}
	if(idx){
		cout<<idx<<' '<<mn<<'\n';
	}else{
		cout<<"-1\n";
	}
}