Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int debug = 1;
- int test = 1;
- #define run if(debug){cout<<__LINE__<<endl;}
- #define BOOST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
- #define no cout<<"NO"<<endl;
- #define yes cout<<"YES"<<endl;
- #define rep(i,n) for(int i=0;i<n;i++)
- #define REP(i,n) for(int i=1;i<=n;i++)
- #define ll long long
- #define inf 1000050000
- //########################################################//
- #define test() int tt=1; if(test){cin>>tt;} while(tt--)
- //###########################################//
- #define trace1(x) cout<<#x<<": "<<x<<endl
- #define trace2(x, y) cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
- #define trace3(x, y, z) cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
- #define trace4(a, b, c, d) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
- #define trace5(a, b, c, d, e) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
- #define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
- //###########################################//
- int main() {
- BOOST
- debug = 0;
- test = 0;
- // 14967
- test()
- {
- run
- int n, m;
- cin >> n >> m;
- run
- vector<vector<int>>dp(5001, vector<int>(5001));
- int b[5001] = {0}, g[5001] = {0};
- run
- REP(i, n)
- {
- cin >> b[i];
- }
- REP(i, m)
- {
- cin >> g[i];
- }
- run
- sort(b, b + n);
- sort(g, g + m);
- for (int i = 0; i <= n; i++)
- {
- for (int j = 0; j <= m; j++)
- {
- if (i == 0 or j == 0)
- {
- dp[i][j] = 0;
- continue;
- }
- dp[i][j] = inf;
- }
- }
- run
- for (int i = 1; i <= n; i++)
- {
- for (int j = i; j <= m; j++)
- {
- int val = dp[i - 1][j - 1] + abs(b[i] - g[j]);
- dp[i][j] = min(dp[i][j] , val);
- // trace4(i, j, dp[i][j], val);
- }
- }
- run
- cout << dp[n][m] << endl;
- }
- }
- /*
- https://pastebin.com/SxMLgTqu
- I used bottom up approach
- am not able to find any mistake
- I downloaded the test case but i wasnt able to run it bcoz of some issue idk what it is
- Please help me Sir / Bhaiya.
- Thanks in Advance
- */
Add Comment
Please, Sign In to add comment