fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define all(v)        ((v).begin()), ((v).end())
  5. #define rep(i, a, b) for (int i = a; i < b; ++i)
  6. #define repd(i, a, b) for (int i = a; i >= b; --i)
  7. #define pb            push_back
  8. #define B             begin()
  9. #define E             end()
  10. #define clr(x)        memset(x,0,sizeof(x))
  11. #define endl          '\n'
  12. #define FASTIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
  13.  
  14. typedef long long ll;
  15. typedef unsigned long long ull;
  16. typedef long double   ld;
  17. typedef pair<int, int> pi;
  18. typedef vector<bool>      vb;
  19. typedef vector<vb>        vvb;
  20. typedef vector<string>    vs;
  21. typedef vector<int>       vi;
  22. typedef vector<ll>       vll;
  23. typedef vector<double>    vd;
  24. typedef vector< vi >      vvi;
  25.  
  26. #ifndef ONLINE_JUDGE
  27. #define deb(...) cerr << "[" << #__VA_ARGS__ << "] = "; _print(__VA_ARGS__); cerr << endl;
  28. #else
  29. #define deb(...)
  30. #endif
  31.  
  32. void _print(ll t) {cerr << t;}
  33. void _print(int t) {cerr << t;}
  34. void _print(bool t) {cerr << t;}
  35. void _print(string t) {cerr << t;}
  36. void _print(char t) {cerr << t;}
  37. void _print(ld t) {cerr << t;}
  38. void _print(double t) {cerr << t;}
  39. void _print(ull t) {cerr << t;}
  40.  
  41.  
  42. template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
  43. template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  44. template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  45. template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}
  46. template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
  47.  
  48. template <typename T, typename... Args>
  49. void _print(T t, Args... args) {_print(t);cerr << ", ";_print(args...);}
  50.  
  51. const int dx[] = {0,0,1,-1};
  52. const int dy[] = {1,-1,0,0};
  53.  
  54. const ll inf = 1e11+1000;
  55. const double eps = (1e-8);
  56. const ll mod = 1e9 + 7;
  57.  
  58. const int N = 3e5, M = 10;
  59. int k, n, m;
  60. vector<ll> primes;
  61. void sieve(int n) {
  62.     // 500ms to get primes up to 1e7 -> ~660000 primes
  63.     bitset<10000> prime; prime.set();
  64.     for (ll p = 2; p * p<= n; p++) {
  65.         if (prime[p]) {
  66.             for (ll i = p * p; i <= n; i += p)
  67.                 prime[i] = false;
  68.         }
  69.     }
  70.     for (int p = 2; p <= n; p++)
  71.         if (prime[p]) primes.pb(p);
  72. }
  73.  
  74. vector<set<int>> primeFact(1010);
  75.  
  76. void PrimeDivisorsRange(ll mxVal, vector<set<int>>& divOf){
  77.     for (ll i = 2; i < mxVal; i++)
  78.     {
  79.         if(divOf[i].size()==0){
  80.             //this number is a prime - have not been reached before
  81.             divOf[i].insert(i);
  82.             for (int j = 2*i; j < mxVal; j+=i)
  83.             {
  84.                 divOf[j].insert(i);
  85.             }
  86.         }
  87.     }
  88. }
  89. void solve(){
  90.     cin>>n>>k;
  91.     vector<pi> v(n);
  92.     rep(i,0,n){
  93.         cin>>v[i].first;
  94.     }
  95.     rep(i,0,n) cin>>v[i].second;
  96.  
  97.     sort(all(v), [&](auto& f, auto& s){
  98.         return f.second < s.second;
  99.     });
  100.     deb(v)
  101.     ll ans = inf;
  102.     rep(i,0,n){
  103.         set<int>& curSet = primeFact[v[i].first];
  104.         vi curVec;
  105.         for(int num: curSet){  
  106.             curVec.pb(num);
  107.         }
  108.         int mask = (1<<(curVec.size())) - 1;
  109.         deb(curVec)
  110.         deb(i, mask)
  111.         vector<vll> val(mask + 1, vll(curVec.size()+2,inf));
  112.         vector<vector<set<int>>> takenInd(mask+1, vector<set<int>>(curVec.size()+2));
  113.  
  114.         val[mask][1] = v[i].second;
  115.         takenInd[mask][1].insert(i);
  116.  
  117.         int taken = 0, brk = 0;
  118.         ll curAns = inf;
  119.  
  120.         for(int j = 0; j < n; j++){
  121.             if(j==i) continue;
  122.             int curMask = 0;
  123.             rep(s,0,curVec.size()){
  124.                 if(primeFact[v[j].first].count(curVec[s])){
  125.                     curMask |= (1<<s);
  126.                 }
  127.             }
  128.             vector<vll> tmp = val;
  129.             rep(s,0,curVec.size()+1){
  130.                 for(int m = 0; m<=mask; m++){
  131.                     if(tmp[m & curMask][s+1] > val[m][s]+v[j].second){
  132.                         tmp[m & curMask][s+1] = min(val[m & curMask][s+1], val[m][s]+v[j].second);
  133.                         takenInd[m&curMask][s+1] = takenInd[m][s];
  134.                         takenInd[m&curMask][s+1].insert(j);
  135.                     }
  136.                 }
  137.             }
  138.             val = tmp;
  139.             rep(s,0,val[0].size()){
  140.                 if(val[0][s]<inf){
  141.                     deb(j, s)
  142.                     taken = s;
  143.                     curAns = val[0][s];
  144.                     rep(l,0,n){
  145.                         if(taken >= k) break;
  146.                         if(!takenInd[0][s].count(l)){
  147.                             taken++;
  148.                             curAns+=v[l].second;
  149.                             // takenInd[0][s].insert(l);
  150.                         }
  151.                     }
  152.                     brk = 1;
  153.                     break;
  154.                 }
  155.             }
  156.             if(brk) break;
  157.         }
  158.         if(taken != k || curAns >= inf) continue;
  159.         // deb(val[0])
  160.         ans = min(ans, curAns);
  161.     }
  162.     cout<<(ans>=inf? -1:ans)<<endl;
  163.  
  164. }
  165.  
  166. int main(){
  167.     FASTIO;
  168.  
  169.     sieve(1010);
  170.     PrimeDivisorsRange(1010, primeFact);
  171.  
  172.     int t = 1;
  173.     cin >> t;
  174.     while(t--)
  175.         solve();
  176.  
  177.     return 0;
  178. }
  179.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
5 4
10 2 5 7 8
7 9 11 2 3
3 1
10 12 3
5 7 9
4 2
1 2 3 4
10 10 7 10
stdout
copy 
21
-1
17
https://ideone.com/KBEbIP
language:
C++14 (gcc 8.3)
created:
14 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!