Guest User

Untitled

a guest
Aug 4th, 2020
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.61 KB | None | 0 0
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. int debug = 1;
  6. int test = 1;
  7. #define run if(debug){cout<<__LINE__<<endl;}
  8.  
  9. #define BOOST ios::sync_with_stdio(false);  cin.tie(NULL); cout.tie(NULL);
  10.  
  11. #define no cout<<"NO"<<endl;
  12. #define yes cout<<"YES"<<endl;
  13. #define rep(i,n) for(int i=0;i<n;i++)
  14. #define REP(i,n) for(int i=1;i<=n;i++)
  15. #define ll long long
  16. #define inf 1000050000
  17. //########################################################//
  18. #define test() int tt=1; if(test){cin>>tt;}  while(tt--)
  19. //###########################################//
  20. #define trace1(x)                cout<<#x<<": "<<x<<endl
  21. #define trace2(x, y)             cout<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
  22. #define trace3(x, y, z)          cout<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
  23. #define trace4(a, b, c, d)       cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
  24. #define trace5(a, b, c, d, e)    cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
  25. #define trace6(a, b, c, d, e, f) cout<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
  26. //###########################################//
  27.  
  28. int main() {
  29.  
  30.     BOOST
  31.  
  32.     debug = 0;
  33.     test = 0;
  34.  
  35. // 14967
  36.  
  37.     test()
  38.     {
  39.         run
  40.  
  41.         int n, m;
  42.         cin >> n >> m;
  43.  
  44.         run
  45.  
  46.         vector<vector<int>>dp(5001, vector<int>(5001));
  47.         int b[5001] = {0}, g[5001] = {0};
  48.  
  49.         run
  50.  
  51.         REP(i, n)
  52.         {
  53.             cin >> b[i];
  54.         }
  55.  
  56.         REP(i, m)
  57.         {
  58.             cin >> g[i];
  59.         }
  60.         run
  61.  
  62.         sort(b, b + n);
  63.         sort(g, g + m);
  64.  
  65.         for (int i = 0; i <= n; i++)
  66.         {
  67.             for (int j = 0; j <= m; j++)
  68.             {
  69.                 if (i == 0 or j == 0)
  70.                 {
  71.                     dp[i][j] = 0;
  72.                     continue;
  73.                 }
  74.                 dp[i][j] = inf;
  75.             }
  76.         }
  77.         run
  78.  
  79.         for (int i = 1; i <= n; i++)
  80.         {
  81.             for (int j = i; j <= m; j++)
  82.             {
  83.                 int val = dp[i - 1][j - 1] + abs(b[i] - g[j]);
  84.                 dp[i][j] = min(dp[i][j] , val);
  85.                 // trace4(i, j, dp[i][j], val);
  86.             }
  87.         }
  88.         run
  89.  
  90.         cout << dp[n][m] << endl;
  91.     }
  92. }
  93.  
  94. /*
  95. https://pastebin.com/SxMLgTqu
  96.  
  97. I used bottom up approach
  98.  
  99. am not able to find any mistake
  100. I downloaded the test case but i wasnt able to run it bcoz of some issue idk what it is
  101.  
  102. Please help me Sir / Bhaiya.
  103.  
  104. Thanks in Advance
  105. */
Add Comment
Please, Sign In to add comment