SHARE
TWEET

Untitled

a guest Jan 26th, 2020 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int main(){
  4.    
  5.     int n;
  6.     cin>>n;
  7.     vector<vector<long long> >a(n+1);
  8.     vector<long long> A(n+1),B(n+1);
  9.     for(int i=1;i<=n;i++){
  10.         cin>>A[i];
  11.     }
  12.     for(int i=1;i<=n;i++){
  13.         cin>>B[i];
  14.     }
  15.    
  16.     for(int i=1;i<=n;i++){
  17.         for(int j=1;j<=n;j++){
  18.             a[i].push_back(__gcd(A[i],B[j]));
  19.         }
  20.         sort(a[i].begin(),a[i].end());
  21.     }
  22.    
  23.    
  24.     vector<long long> u (n+1), v (n+1), p (n+1), way (n+1);
  25. for (int i=1; i<=n; ++i) {
  26.     p[0] = i;
  27.     int j0 = 0;
  28.     vector<long long> minv (n+1,10000);
  29.     vector<char> used (n+1, false);
  30.     do {
  31.         used[j0] = true;
  32.         long long i0 = p[j0],  delta = 10000,  j1=0;
  33.         for (int j=1; j<=n; ++j)
  34.             if (!used[j]) {
  35.                 int cur = a[i0][j]-u[i0]-v[j];
  36.                 if (cur < minv[j])
  37.                     minv[j] = cur,  way[j] = j0;
  38.                 if (minv[j] < delta)
  39.                     delta = minv[j],  j1 = j;
  40.             }
  41.         for (int j=0; j<=n; ++j)
  42.             if (used[j])
  43.                 u[p[j]] += delta,  v[j] -= delta;
  44.             else
  45.                 minv[j] -= delta;
  46.         j0 = j1;
  47.     } while (p[j0] != 0);
  48.     do {
  49.         int j1 = way[j0];
  50.         p[j0] = p[j1];
  51.         j0 = j1;
  52.     } while (j0);
  53.    
  54.    
  55. }
  56.    
  57. long long cost = -v[0];
  58. cout<<cost;
  59. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top