2D Prefix Sum

/*PROBLEM: Sayan's friend has left a gamefield organized as an N∗N grid. Each square in the grid either has
           or does not have a gold coin. He has to divide the gamefield with his three other friends as
           follows:
           he will draw one horizontal line and one vertical line to divide the field into four rectangles. His friends will choose three of the four smaller fields and he gets the last one.

He wants to divide the field so that he gets the maximum number of goldcoins, assuming that his friends
will pick the best three rectangles (i.e. 𝑺𝒂𝒚𝒂𝒏 𝒘𝒊𝒍𝒍 𝒂𝒍𝒘𝒂𝒚𝒔 𝒈𝒆𝒕 𝒕𝒉𝒆 𝒓𝒆𝒄𝒕𝒂𝒏𝒈𝒍𝒆 𝒉𝒂𝒗𝒊𝒏𝒈 𝒎𝒊𝒏𝒊𝒎𝒖𝒎 #𝒈𝒐𝒍𝒅 𝒄𝒐𝒊𝒏𝒔).

Input Format:
The first line contains 2 integers N and M, the size of the gamefield and the number of gold coins in the
field respectively.

The next M lines contain two integers, Xi and Yi, giving the coordinated of the i-th gold coin. It is guaranteed that all Xi and Yi are pairwise distinct.

Constraints:
1 ≤ N ≤ 1000
0 ≤ M ≤ N²
1 ≤ Xᵢ,Yᵢ ≤ N

Output Format:
Output one integer, the maximum number of gold coins Sayan can get.

Sample Input:
	6 13
	1 2
	1 3
	2 1
	2 4
	2 5
	3 2
	4 2
	4 3
	4 6
	5 1
	5 4
	5 5
	6 2

Sample Output: 3
*/

/*UNDERLYING CONCEPT ----->
  # This problem is based on the concept of 2 - D Prefix Sum.
  # ∴ a dp[][] matrix will be formed where dp[i][j] stores the total number of gold coins present in the
    submatrix whose left upper cell is dp[0][0] and lower right cell is dp[i][j].
    The above precomputation is done in O(n * m) time, where n and m are the #rows and #columns in the i/p
    matrix.
  # After the above precomputation just traverse the dp[][] matrix by considering each case when Sayan divide
    the matrix at the current dp[i][j] cell. The minimum of the 4 parts is taken as 𝑺𝒂𝒚𝒂𝒏 𝒘𝒊𝒍𝒍 𝒂𝒍𝒘𝒂𝒚𝒔 𝒈𝒆𝒕
    𝒕𝒉𝒆 𝒓𝒆𝒄𝒕𝒂𝒏𝒈𝒍𝒆 𝒉𝒂𝒗𝒊𝒏𝒈 𝒎𝒊𝒏𝒊𝒎𝒖𝒎 #𝒈𝒐𝒍𝒅 𝒄𝒐𝒊𝒏𝒔, and then this minimum value is maximized.
*/

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> dp(1001, vector<int>(1001, 0));

void twoDPrefixSum(int n, int m)
{
	for(int i=1; i<n; i++)
	   dp[i][0]+=dp[i-1][0];

    for(int j=1; j<m; j++)
	   dp[0][j]+=dp[0][j-1];

	for(int i=1; i<n; i++)
	{
		for(int j=1; j<m; j++)
           dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
    }
}

bool comp(int a, int b)
{
       return (a < b);
}

void solve()
{
	int n, m; cin>>n>>m;
	for(int i=0; i<m; i++)
	{
		int x, y; cin>>x>>y;
		dp[x-1][y-1]=1;
	}

	twoDPrefixSum(n, n);

	int res=INT_MIN;

	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
		{
			int part1=dp[i][j];
			int part2=dp[i][n-1] - dp[i][j];
			int part3=dp[n-1][j] - dp[i][j];
			int part4=dp[n-1][n-1] - (part1 + part2 + part3);

			res=max(res, min({part1, part2, part3, part4}, comp));
		}
	}

	cout<<res;
}

int main() {

    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    srand(chrono::high_resolution_clock::now().time_since_epoch().count());

    int t = 1;
    //cin >> t;
    while(t--) {
      solve();
    }

    return 0;
}

/*# Time complexity: O(r*c), where r and c are the #rows and #columns in the given i/p 2 D Matrix.
  # Auxiliary Space: O(r*c), where r and c are the #rows and #columns in the given 2 D Matrix.
*/