Can someone help in this question?
Difference between en1 and en2, changed 10 character(s)

there are n places in hackerland and a delivery person can visit the places in exactly m days. The delievery person can start from any of the n places and gets an extra profit for visiting a place . Given a matrix profit of dimensions n*m , if the jth visit of the delievery person is at ith place , the profit increases by profit[i][j]. If the delievery person is currently at ith place , the next place that can be reached is between i-k and i+k . in other words the delievery person can travel to places that are at most k units distance from current place in one day. note that a place can be visited multiple times. determine the maximum profit the delievery person can make by visiting the places optimally over m.↵

example : n=3,m=3,k=1↵
profit=[[1,3,1],[2,3,1],[1,1,4]]↵
ans : 8↵

Explanation- The delivery person can go to any location on day 1.↵
The highest value in the first index is 2 found at location 2. Try starting there.↵
The next day, locations 1 or 3 can be visited.↵
Visit is to location 1, the added profit is 3.↵
This leaves only location 2 within reach for the last day with a profit of 3.↵
The total profit from this route is 2+3+3=8.↵
Visit location 3, the profit is 1. ↵
Again, only location 2 can be reached on the last day with a profit of 3. ↵
The total profit is 2+1+3=6.↵
Return 8, the maximum possible profit↵

example 2 — n=3,m=3,k=1↵
profit =[[1,6,3],[2,4,4],[3,3,1]]↵
ans : 12↵

Explanation↵

The journey starts at place 2 which offers a profit of 2. Then the next day the delivery person visits place 1 to get a profit of 6 and on the last day, revisits place 2 to get a profit of 4. Total sum=2+6+4=12↵

constraints: 1<=n,m<=1e5
 ,
2<=n*m<=2*1e5
 , 
1<=k<=n
 , 
1<=profit[i][j]<=1e9

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English kyu_12 2023-09-24 23:11:27 10
en1 English kyu_12 2023-09-24 23:10:39 1761 Initial revision (published)