Guys,can anyone help me regarding this problem,i mean how to appproach this problem?

Initially,i wrote a greedy solution but that didn’t work,later found out this is a dp problem.

Any kind of explanation would be appreciated

First find the prefix sums of each row and column, Then using that find the prefix sum of the grid.

## Code for prefix sums

```
vector<vector<pair<int,int>>> prefix_sum(n+1, vector<pair<int,int>>(m+1, mp(0,0)));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
prefix_sum[i][j].first=prefix_sum[i-1][j].first+grid[i-1][j-1];
prefix_sum[i][j].second=prefix_sum[i][j-1].second+grid[i-1][j-1];
}
}
//prefix_sum[i][j].first is the sum of i elements in the jth column
//prefix_sums[i][j].second is the sum of j elements in the ith row.
vector<vector<int>> gridsum(n+1, vector<int>(m+1, 0));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
gridsum[i][j]=gridsum[i-1][j-1]+prefix_sum[i][j].first + prefix_sum[i][j].second - grid[i-1][j-1];
}
}
//gridsum[i][j] is the sum of grid[a][b] where a<i and b<j
```

Then find the no. of people annoyed, and the area searched by each blackout.

## How to find that

```
vector<pair<int,int>> blackouts(q);
for(auto &x: blackouts){
int a,b,c,d;
cin>>a>>b>>c>>d;
//Note gridsum[a][b] = sum of grid[i][j] where i<a and j<b
//x.first is people annoyed
x.first=gridsum[c][d] -gridsum[c][b-1] - gridsum[a-1][d] + gridsum[a-1][b-1];
x.second=(d-b+1)*(c-a+1);
//x.second is area covered
}
```

Then do a dp, that finds the maximum area searched if you annoy k people.

## Dp relation

```
vector<int> dp(k+1, 0);
int ans=0;
for(const auto &x : blackouts){
for(int i=k;i>=x.first;i--){
//x.first is people annoyed, and x.second is area covered
dp[i]=max(dp[i], dp[i-x.first] + x.second);
ans=max(ans, dp[i]);
}
}
cout<<ans;
```

The dp cannot be done from x.first to k, since the previous dp states may have used this blackout, and that would double count this blackout.

1 Like

Thankyou so much man,this might be one of the best explanations i have ever encountered