➤ Problem Link : 1060C. Maximum Subrectangle
✅ C++ Solution :
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
bool func(ll i, ll b[], ll m, ll p, ll x)
{
if(i>m)
return 0;
ll mn=LONG_MAX;
ll curr=0;
ll k;
for(k=0;k<i;k++)
curr+=b[k];
mn=min(mn,curr);
for(;k<m;k++)
{
curr=curr+b[k]-b[k-i];
mn=min(mn,curr);
}
return mn*p <= x ;
}
int main()
{
int n,m;
cin>>n>>m;
ll a[n],b[m];
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<m;i++)
cin>>b[i];
ll x;
cin>>x;
ll mn,low=0,mid,high=m;
ll ans=0;
for(ll i=1;i<=n;i++)
{
mn=LONG_MAX;
ll curr=0;
ll k;
for(k=0;k<i;k++)
curr+=a[k];
mn=min(mn,curr);
for(;k<n;k++)
{
curr=curr+a[k]-a[k-i];
mn=min(mn,curr);
}
low=0,high=m;
while(low<high)
{
mid=low+(high-low+1)/2;
if(func(mid,b,m,mn,x))
low=mid;
else
high=mid-1;
}
ans=max(ans,high*i);
}
cout<<ans;
}
Thank you for your patience reading. If you enjoyed this post, I’d be very grateful if you’d help it spread by emailing it to a friend, or sharing it on Whatsapp or Facebook.
😇Happy Learning!!
I am a Member Technical at D.E. Shaw India Pvt. Ltd. CodingWithArt is a blog where you find tricks and solutions to challenging coding and development problems. I aim to build a universal tech platform for every enthusiast out there.