Valentine magic problem(last vedio of Dynamic Programming)

/valentine magic
#include<bits/stdc++.h>
#define ll long long
#define INF 10009876655433;

using namespace std;
// i is the index for boy and j is for girl

int dp[5005][5005];
ll a[5005];
ll b[5005];
ll n,m;
ll f(ll i,ll j)
{

//base case
if(i==n)
{
    //we have paired all the boys
    return 0;
}
    if(j==m)
    {
        //we have rejected lott of girls and now no girl is available
        return -1;
    }

    if(dp[i][j]!=-1)
    {
        return dp[i][j];
    }
    int op1=abs(a[i]-b[j])+ f(i+1,j+1);//by accepting the jth girl
    int op2=f(i,j+1);//by rejecting the jth girl

    return dp[i][j]=min(op1,op2);

}

int main()
{
memset(dp,-1,sizeof(dp));
cin>>n>>m;

for(int i=0;i<n;i++)
cin>>a[i];

for(int j=0;j<m;j++)
cin>>b[j];

sort(a,a+n);
sort(b,b+m);
ll ans=f(0,0);
cout<<ans<<endl;
return 0;

}
//the code is not giving correct output
suppose
input:
2 5
4 5
1 2 3 4 5
output :
-1
but output should be 0

@hrit04
Please send your code on CB IDE

sir how to send my code on CB IDE?
I have compile and run the code on CB IDE but dont know how to share?
Please help me to share.

@hrit04 buddy
Just paste your code on the IDE
Then click on save
Then send the URL here

@hrit04
Small issue
Line 24
You’re making not having any girls more favourable by returning -1 in a problem where you have to do minimisation
So you need to either check for -1 and ignore that case or return some large positive value like INT_MAX/2

yeaa.Got it.Thanks a lot

1 Like

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.