fork download
copy 
  1. // C++ program to find Largest Sum Contiguous
  2. // Subarray in a given range with updates
  3. #include <bits/stdc++.h>
  4. #include <cstdint>
  5. using namespace std;
  6.  
  7. #define int long long
  8. // Structure to store
  9. // 4 values that are to be stored
  10. // in the nodes
  11. struct node {
  12. 	int sum, prefixsum, suffixsum, maxsum;
  13. };
  14.  
  15. // array to store the segment tree
  16. const int N = 1e5+5;
  17. node tree[4 * N];
  18.  
  19. // function to build the tree
  20. void build(int arr[], int low, int high, int index)
  21. {
  22. 	// the leaf node
  23. 	if (low == high) {
  24. 		tree[index].sum = arr[low];
  25. 		tree[index].prefixsum = arr[low];
  26. 		tree[index].suffixsum = arr[low];
  27. 		tree[index].maxsum = arr[low];
  28. 	}
  29. 	else {
  30. 		int mid = (low + high) / 2;
  31.  
  32. 		build(arr, low, mid, 2 * index + 1);
  33.  
  34. 		build(arr, mid + 1, high, 2 * index + 2);
  35.  
  36. 		tree[index].sum = tree[2 * index + 1].sum +
  37. 						tree[2 * index + 2].sum;
  38.  
  39. 		tree[index].prefixsum =
  40. 					max(tree[2 * index + 1].prefixsum,
  41. 					tree[2 * index + 1].sum +
  42. 					tree[2 * index + 2].prefixsum);
  43.  
  44. 		tree[index].suffixsum =
  45. 					max(tree[2 * index + 2].suffixsum,
  46. 					tree[2 * index + 2].sum +
  47. 					tree[2 * index + 1].suffixsum);
  48. 		tree[index].maxsum =
  49. 					max(tree[index].prefixsum,
  50. 					max(tree[index].suffixsum,
  51. 					max(tree[2 * index + 1].maxsum,
  52. 					max(tree[2 * index + 2].maxsum,
  53. 					tree[2 * index + 1].suffixsum +
  54. 					tree[2 * index + 2].prefixsum))));
  55. 	}
  56. }
  57.  
  58. void update(int arr[], int index, int low, int high,
  59. 			int idx, int value)
  60. {
  61. 	if (low == high) {
  62. 		tree[index].sum = value;
  63. 		tree[index].prefixsum = value;
  64. 		tree[index].suffixsum = value;
  65. 		tree[index].maxsum = value;
  66. 	}
  67. 	else {
  68.  
  69. 		int mid = (low + high) / 2;
  70.  
  71. 		if (idx <= mid)
  72. 			update(arr, 2 * index + 1, low, mid, idx, value);
  73. 		else
  74. 			update(arr, 2 * index + 2, mid + 1,
  75. 				high, idx, value);
  76.  
  77. 		tree[index].sum = tree[2 * index + 1].sum +
  78. 						tree[2 * index + 2].sum;
  79.  
  80. 		tree[index].prefixsum =
  81. 					max(tree[2 * index + 1].prefixsum,
  82. 					tree[2 * index + 1].sum +
  83. 					tree[2 * index + 2].prefixsum);
  84.  
  85. 		tree[index].suffixsum =
  86. 					max(tree[2 * index + 2].suffixsum,
  87. 					tree[2 * index + 2].sum +
  88. 					tree[2 * index + 1].suffixsum);
  89.  
  90. 		tree[index].maxsum =
  91. 					max(tree[index].prefixsum,
  92. 					max(tree[index].suffixsum,
  93. 					max(tree[2 * index + 1].maxsum,
  94. 					max(tree[2 * index + 2].maxsum,
  95. 					tree[2 * index + 1].suffixsum +
  96. 					tree[2 * index + 2].prefixsum))));
  97. 	}
  98. }
  99.  
  100. node query(int arr[], int index, int low,
  101. 		int high, int l, int r)
  102. {
  103. 	node result;
  104. 	result.sum = result.prefixsum =
  105. 				result.suffixsum =
  106. 				result.maxsum = INT64_MIN;
  107.  
  108. 	if (r < low || high < l)
  109. 		return result;
  110.  
  111. 	if (l <= low && high <= r)
  112. 		return tree[index];
  113.  
  114. 	int mid = (low + high) / 2;
  115.  
  116. 	if (l > mid)
  117. 		return query(arr, 2 * index + 2,
  118. 					mid + 1, high, l, r);
  119.  
  120. 	if (r <= mid)
  121. 		return query(arr, 2 * index + 1,
  122. 					low, mid, l, r);
  123.  
  124. 	node left = query(arr, 2 * index + 1,
  125. 					low, mid, l, r);
  126. 	node right = query(arr, 2 * index + 2,
  127. 						mid + 1, high, l, r);
  128.  
  129. 	result.sum = left.sum + right.sum;
  130. 	result.prefixsum = max(left.prefixsum, left.sum +
  131. 						right.prefixsum);
  132.  
  133. 	result.suffixsum = max(right.suffixsum,
  134. 					right.sum + left.suffixsum);
  135. 	result.maxsum = max(result.prefixsum,
  136. 					max(result.suffixsum,
  137. 					max(left.maxsum,
  138. 					max(right.maxsum,
  139. 					left.suffixsum + right.prefixsum))));
  140.  
  141. 	return result;
  142. }
  143.  
  144. signed main()
  145. {
  146.     int t; 
  147.     cin>>t; 
  148.     while(t--)
  149.     {
  150.         int n,q;
  151.         cin>>n>>q;
  152.         int T[n],Q[n]; 
  153.         memset(T,0,sizeof(T));
  154.         build(T,0,n-1,0);
  155.         for(int i=0;i<n;i++)
  156.         {
  157.             cin>>T[i];
  158.         }
  159.         for(int i=0;i<n;i++)
  160.         {
  161.             cin>>Q[i];
  162.         }
  163.         build(T,0,n-1,0);
  164.  
  165.         int maxi=0;
  166.         for(int i=0;i<n;i++)
  167.         {
  168.             if(Q[i]<0)
  169.             {
  170.                 Q[i]=0;
  171.             }
  172.             int temp = T[i];
  173.             T[i]+=(q*Q[i]);
  174.             update(T, 0, 0, n - 1, i, T[i]);
  175.             maxi = max(query(T, 0, 0, n - 1, 0, n-1).maxsum,maxi);
  176.             T[i]=temp; 
  177.             update(T,0,0,n-1,i,temp);
  178.  
  179.         }
  180.  
  181.         cout<<maxi<<"\n";
  182.     }
  183. 	return 0;
  184. }
  185.  
Success #stdin #stdout 0s 5584KB
comments (?)
stdin
copy 
4
4 2
1 2 3 4
5 1 3 2
3 1
-3 2 -10
1 1 200
5 3
-1 -1 10 -1 -1
-3 -3 -3 -3 -3
3 1
2 -1 2
-1 -1 -1
stdout
copy 
20
192
10
3
https://ideone.com/Mk7zXX
language:
C++14 (gcc 8.3)
created:
2 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!