fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <algorithm>
  6. #include <utility>
  7. #include <map>
  8. #include <set>
  9. #include <string>
  10. #include <cstring>
  11. #include <queue>
  12. #define rf freopen("in.in", "r", stdin)
  13. #define wf freopen("out.out", "w", stdout)
  14. #define rep(i, s, n) for(int i=int(s); i<=int(n); ++i)
  15. using namespace std;
  16. const int mx = 1e5 + 10, mod = 1e9+7;
  17.  
  18. int n, m;
  19. int buying[1111][1111], selling[1111][1111];
  20. long double dp[1111][1111][2];
  21. long long d;
  22.  
  23. int main()
  24. {
  25. 	//rf;// wf;
  26. 	ios::sync_with_stdio(0);
  27.  
  28. 	cin >> n >> m >> d;
  29. 	for(int i = 0; i<n; ++i)
  30. 	{
  31. 		for(int j = 0; j<m; ++j)
  32. 			cin >> selling[j][i] >> buying[j][i];
  33. 	}
  34.  
  35. 	for(int i = 0; i<n; ++i)
  36. 		dp[0][i][0] = d,
  37. 		dp[0][i][1] = 0;
  38.  
  39. 	for(int t = 1; t <= m; ++t)
  40. 	{
  41. 		for(int i = 0; i<n; ++i)
  42. 		{
  43. 			dp[t][i][0] = dp[t-1][i][0];
  44. 			dp[t][i][1] = dp[t-1][i][1];
  45.  
  46. 			for(int dis = 1; dis <= 1; ++dis)
  47. 			{
  48. 				if(i+dis < n)
  49. 				{
  50. 					dp[t][i][0] = max(dp[t][i][0], dp[t-dis][i+dis][0]);
  51. 					dp[t][i][1] = max(dp[t][i][1], dp[t-dis][i+dis][1]);
  52.  
  53. 					dp[t][i][0] = max(dp[t][i][0], dp[t-1][i][1]*buying[t-1][i]);
  54. 					dp[t][i][1] = max(dp[t][i][1], dp[t-1][i][0]/selling[t-1][i]);
  55. 				}
  56. 				if(i-dis >= 0)
  57. 				{
  58. 					dp[t][i][0] = max(dp[t][i][0], dp[t-dis][i-dis][0]);
  59. 					dp[t][i][1] = max(dp[t][i][1], dp[t-dis][i-dis][1]);
  60.  
  61. 					dp[t][i][0] = max(dp[t][i][0], dp[t-1][i][1]*buying[t-1][i]);
  62. 					dp[t][i][1] = max(dp[t][i][1], dp[t-1][i][0]/selling[t-1][i]);
  63. 				}
  64. 			}
  65. 		}
  66. 	}
  67.  
  68. 	long double ans = 0;
  69. 	for(int i = 0; i<n; ++i)
  70. 		ans = max(ans, dp[m][i][0]);
  71.  
  72. 	if(ans > 1e18)
  73. 		printf("Quintillionnaire\n");
  74. 	else
  75. 		printf("%.7Lf\n", ans);
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 42032KB
comments (?)
stdin
copy 
3 3 5
2 1 5 3 7 6
2 1 4 3 6 5
10 9 8 7 6 5
stdout
copy 
15.0000000
https://ideone.com/RegM6V
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!