fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// your code goes here
  6. 	int n;
  7. 	cin>>n;
  8. 	int arr[n], brr[n];
  9. 	for(int i = 0; i < n; i++)
  10. 	cin>>arr[i];
  11.  
  12. 	for(int i = 0; i < n; i++)
  13. 	cin>>brr[i];
  14.  
  15.  
  16. 	int ans = 0;
  17. 	int pre[n];
  18.  
  19. 	int suff[n];
  20.  
  21. 	pre[0] = arr[0]*brr[0];
  22. 	for(int i = 1; i < n; i++)
  23. 	pre[i] = pre[i - 1] + arr[i] * brr[i];
  24.  
  25.  
  26.  
  27. 	suff[n - 1] = arr[n - 1] * brr[n - 1];
  28.  
  29. 	for(int i = n - 2; i >= 0; i--)
  30. 	suff[i] = suff[i + 1] + arr[i] * brr[i];
  31.  
  32. 	int dp[n][n];
  33.  
  34. 	for(int i = 0; i < n; i++)
  35. 	{
  36. 		for(int j = i; j < n; j++)
  37. 		{
  38. 			dp[i][j] = 0;
  39. 			if(i == j)
  40. 			dp[i][j] = arr[i] * brr[i];
  41.  
  42. 			if(j - i + 1 == 2)
  43. 			{
  44. 				dp[i][j] = arr[i]*brr[j] + arr[j]*brr[i];
  45.  
  46. 			}
  47.  
  48. 		}
  49. 	}
  50. 	for(int len = 3; len <= n; len++)
  51. 	{
  52.  
  53.  
  54. 		for(int i = 0; i <= n- len; i++)
  55. 		{
  56. 			int j = i + len - 1;
  57. 			dp[i][j] = arr[i]*brr[j] + arr[j] * brr[i];
  58. 			dp[i][j]+= dp[i + 1][j - 1];
  59. 		}
  60. 	}
  61.  
  62.  
  63.  
  64.  
  65.  
  66.  
  67.  
  68.  
  69. 	for(int i = 0; i < n; i++)
  70. 	{
  71. 		int sum = 0;
  72. 		for(int j = i; j < n; j++)
  73. 		{
  74. 			//
  75. 			int cnt = 0;
  76. 			if(i > 0)
  77. 			cnt+= pre[i - 1];
  78.  
  79. 			if(j < n - 1)
  80. 			cnt-= suff[j + 1];
  81.  
  82. 			cnt+= dp[i][j];
  83.  
  84. 			ans = max(ans, cnt);
  85.  
  86.  
  87.  
  88.  
  89. 		}
  90. 	}
  91. 	cout<<ans<<endl;
  92. 	return 0;
  93. }
Success #stdin #stdout 0.01s 5508KB
comments (?)
stdin
copy 
6
1 8 7 6 3 6
5 9 6 8 8 6
stdout
copy 
233
https://ideone.com/lLMu0Q
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

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!