icpc kolkata solution

acm-icpc
kolkata
online

#1

Hey guys, Can anyone give an approach or link their soln for 2nd problem of icpc kolkata online round ‘Finding Hardest Sum Value’ ?
https://www.codechef.com/ACMKOL15/problems/KOL15B


#2

Perform maximum sum subarray DP for each of the N*M points in all 4 directions. It can be done in O(4 * N * M) time. Now, iterate through each point in matrix, fixing it as meeting point of all 4 persons. Each point’s optimal value can be found in O(1) time, using the already computed values. Find the best point and report its value


#3

Thanks…
Still new gotta learn more dp algos
Btw that O(4 * N * M) time for computing subarrays for all n*m points??
Each direction max subarray dp will take O(N) time too right??
So should,nt it be O(4 * N * N * M )