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.  
  110.         vector<vll> val(mask + 1, vll(curVec.size()+2,inf));
  111.         vector<vector<set<int>>> takenInd(mask+1, vector<set<int>>(curVec.size()+2));
  112.  
  113.         val[mask][1] = v[i].second;
  114.         takenInd[mask][1].insert(i);
  115.  
  116.         int taken = 0, brk = 0;
  117.         ll curAns = inf;
  118.  
  119.         for(int j = 0; j < n; j++){
  120.             if(j==i) continue;
  121.             int curMask = 0;
  122.             rep(s,0,curVec.size()){
  123.                 if(primeFact[v[j].first].count(curVec[s])){
  124.                     curMask |= (1<<s);
  125.                 }
  126.             }
  127.             vector<vll> tmp = val;
  128.  
  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.  
  133.                         tmp[m & curMask][s+1] = min(val[m & curMask][s+1],
  134.                          val[m][s]+v[j].second);
  135.  
  136.                         takenInd[m&curMask][s+1] = takenInd[m][s];
  137.                         takenInd[m&curMask][s+1].insert(j);
  138.                     }
  139.                 }
  140.             }
  141.  
  142.             val = tmp;
  143.  
  144.             rep(s,0,val[0].size()){
  145.                 if(val[0][s]<inf){
  146.                     deb(j, s)
  147.                     taken = s;
  148.                     curAns = val[0][s];
  149.                     rep(l,0,n){
  150.                         if(taken >= k) break;
  151.                         if(!takenInd[0][s].count(l)){
  152.                             taken++;
  153.                             curAns+=v[l].second;
  154.                             // takenInd[0][s].insert(l);
  155.                         }
  156.                     }
  157.                     brk = 1;
  158.                     break;
  159.                 }
  160.             }
  161.             if(brk) break;
  162.         }
  163.         if(taken != k || curAns >= inf) continue;
  164.         // deb(val[0])
  165.         ans = min(ans, curAns);
  166.     }
  167.     cout<<(ans>=inf? -1:ans)<<endl;
  168.  
  169. }
  170.  
  171. int main(){
  172.     FASTIO;
  173.  
  174.     sieve(1010);
  175.     PrimeDivisorsRange(1010, primeFact);
  176.  
  177.     int t = 1;
  178.     cin >> t;
  179.     while(t--)
  180.         solve();
  181.  
  182.     return 0;
  183. }
  184.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/ocwuSe
language:
C++14 (gcc 8.3)
created:
5 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!