How should i approach

rk221_b · September 16, 2019, 2:19pm

What should be my approach to solve this problem…??

Robin_rst · September 17, 2019, 10:34am

Just take prefix sum of every row and after that take prefix sum of every column.
Then if you partition the (i,j)th of grid then your top-left box sum will be the value at (i,j)th index of grid
and top-right box sum will be the sum at that row’s last column - the sum of top-left box sum
and bottom right box sum will be the value at (n,j)th of the grid - the sum of top-left box
and bottom-right box sum will be the value at (n,m)th of grid - top-right box sum - bottom left box sum + the sum of the top-left box ( because it gets subtracted two times, the first time in top-right box sum and the second time in bottom-left box sum ).
Make ans at every step as
ans = max ( ans, min( all four boxes) );
You can see my implementation, I have commented on the part for better understanding. It’s better if you try on a notebook with one small example to have a crystal clear understanding.

github.com

robinrst/Dynamic-Programming/blob/master/GoldCoinDP.cpp

#include "bits/stdc++.h"

using namespace std;

#define  f first
#define  lgn 25
#define  endl '\n'
#define  sc second
#define  N (int)1e3+5
#define  sz(x) x.size()
#define  int long long int
#define  ld long double
#define  vi vector<int>
#define  vs vector<string>
#define  vc vector<char>
#define  mii map<int,int>
#define  pii pair<int,int>
#define  vpii vector<pii>
#define  test(x) while(x--)
#define  pb push_back

This file has been truncated. show original

Robin_rst · September 18, 2019, 7:40pm

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.