You need to find the maximum possible side length of the base of the garden such that the total cost of removing residential plot does not exceed B.
Input Format
Input 1: It will be string which tells two integers separated by a single comma that represent M and N respectively.
Input 2: It will be the integer B, the maximum cost you can afford (i.e., your budget). It is the cost of removing ith plot.
Input 3: It will be the integer P, the residential plots found in the list.
Input 4: It will be string array where:
The first line of the array tells the total number of elements in the array i.e.
Each of the next P lines describes a residential plot. The ith of these lines describes the ith plot. Each line consists of 5 integers: Xi1, Yi1, Xi2, Yi2, and Ci separated by single comma. They represent respectively the coordinates of the bottommost, leftmost cell of the plot, the coordinates of the topmost & rightmost cell of the plot, and the cost of removing the plot. The bottommost, leftmost cell on the grid has coordinates (1, 1) and the topmost, rightmost cell has coordinates (M, N).
1 <= Xi1 <= Xi2 <= M, X coordinates of the leftmost and the rightmost cells of the ith residential plot
1 <= Yi1 <= Yi2 <= N, Y coordinates of the bottommost and the topmost cells of the ith residential plot
Constraints
1 <= M, N <= 1,000,000
1 <= Ci <= 7,000
0 <= B <= 1,00,000
1<= P <= 1,00,000
Output Format
It will be an integer that tells the maximum length of the base of the garden such that the total cost of removing plots does not exceed B.
Sample TestCase 1
Input
6,9
42
5
5
4,1,6,3,12
3,6,5,6,9
1,3,3,8,24
3,8,6,9,21
5,1,6,2,20
Output
4
Explanation: two possible locations for the garden base, both having a side of length 4 which is the maximum possible length of the base of the garden. Hence the output will be 4.
Sample TestCase 2
Input
6,9
0
5
5
4,1,6,3,12
3,6,5,6,9
1,3,3,8,24
3,8,6,9,21
5,1,6,2,20
Output
Code:
#include
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double db;
int main()
{
ll n,m;char ch;ll i,j,k;
cin>>n>>ch>>m;
ll a[n+1][m+1];
ll cost,plots,ui,r1,r2,c1,c2,plotcost;
cin>>cost>>plots>>ui;
vector costv;
costv.push_back(0LL);
ll mp[n+1][m+1];
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
mp[i][j]=0;//<<" “;
}
//cout<<endl;
}
while(plots–)
{
cin>>r1>>ch>>c1>>ch>>r2>>ch>>c2>>ch>>plotcost;
costv.push_back(plotcost);
ll yu=costv.size()-1;
for(i=r1;i<=r2;i++)
{
for(j=c1;j<=c2;j++)
{
mp[i][j]=yu;
}
}
}
ll len;
ll maxlength=0;
ll l;ll s=0;
//cout<<n<<” "<<m<<endl;
for(len=1;len<=6;len++)
{
for(i=1;i<=n-len+1;i++)
{
for(j=1;j<=m-len+1;j++)
{
ll costsum=0;
set se;
for(k=i;k<i+len;k++)
{
for(l=j;l<j+len;l++)
{
se.insert(mp[k][l]);
}
}
for(auto it=se.begin();it!=se.end();it++)
{
costsum+=costv[*it];
}
if(costsum<=cost)
{
maxlength=max(maxlength,len);
}
}
}
}
cout<<maxlength<<endl;
return 0;
}