kotadiyameet173's blog

By kotadiyameet173, history, 5 hours ago, In English

You are given two arrays of size n. You need to choose the sub-array from the first array and replace it with a corresponding sub-array from the second array. Now, find the maximum consecutive sub-array sum in the modified first array.

Sample Input 1-

2

4 -2

1 2

Sample Output 1-

6

Sample Input 2-

8

-2 2 -3 1 -1 -1 1 0

4 -3 3 3 2 -5 3 4

Sample Output 2-

12

  • Vote: I like it
  • -5
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kotadiyameet173 (previous revision, new revision, compare).

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

dp[ind][can][cant]

can is 1 if we are replacing subarray ending at ind-1 and hence we can continue replacing now

cant is 1 if we have already replaced the subarray at index j<ind-1 and hence we can't replace now

»
4 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone already posted this https://mirror.codeforces.com/blog/entry/138331, you can find the solution in the comments