Getting wrong ans

#1

#include<bits/stdc++.h>
using namespace std;
int a[5000],b[5000],dp[5000][5000];
int boys,girls;

int f(int i,int j){
if(i==boys){
return 0;
}
if(j==girls){
return INT_MAX;
}
if(dp[i][j]!=-1){
return dp[i][j];
}

int x = abs(a[i]-b[j]) + f(i+1,j+1);
int y = f(i,j+1);
return dp[i][j] = min(x,y);

}

int main()
{

memset(dp,-1,sizeof(dp));
cin>>boys>>girls;
for(int i=0;i<boys;i++){
    cin>>a[i];
}
for(int i=0;i<girls;i++){
    cin>>b[i];
}
sort(a,a+boys);
sort(b,b+girls);

cout<<f(0,0)<<endl;

}

#3

Your code seems to be almost correct here are few things I suggest changing.

  • First, You should declare the DP and input arrays a little bigger than the given constraints. You declared of size 5000 which means it has indexes upto 4999 and not 5000.
  • Second, You should use the type long long whenever dealing with INT_MAX as you used in your code. This is because even adding as little as 1 to it, will make the value negative due to overflow and you’ll get wrong answer.
#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll a[5005], b[5005], dp[5005][5005];
int boys, girls;

ll f(int i, int j) {
    if (i == boys) {
        return 0;
    }
    if (j == girls) {
        return INT_MAX;
    }
    if (dp[i][j] != -1) {
        return dp[i][j];
    }
    ll x = abs(a[i] - b[j]) + f(i + 1, j + 1);
    ll y = f(i, j + 1);
    return dp[i][j] = min(x, y);
}

int main() {

    memset(dp, -1, sizeof(dp));
    cin >> boys >> girls;
    for (int i = 0; i < boys; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < girls; i++) {
        cin >> b[i];
    }
    sort(a, a + boys);
    sort(b, b + girls);
    cout << f(0, 0) << endl;
}
#4

Hey! check if this resolves your issue.