fork(2) download 
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <complex>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <string>
  8. #include <vector>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <map>
  12. #include <set>
  13. using namespace std;
  14. //#pragma comment(linker,"/STACK:102400000,102400000")
  15. int n, N; 
  16. int x[301]; 
  17. int cost[301]; 
  18. int ans = 1000000000;
  19.  
  20. int m[301];
  21. int DP[301][1<<9];
  22.  
  23. int dp(int cur, int mask)
  24. {
  25. 	if(cur == n+1)
  26. 	{
  27. 		if(mask == (1<<N)-1)
  28. 			return 0;
  29. 		return 1000000000;
  30. 	}
  31. 	int &ret = DP[cur][mask];
  32. 	if(ret != -1) return ret;
  33. 	ret = 1000000000;
  34. 	ret = min(ret, dp(cur + 1, mask));
  35. 	ret = min(ret, dp(cur + 1, mask | m[cur]) + cost[cur]);
  36. 	return ret;
  37. }
  38.  
  39. int MAIN() 
  40. { 
  41.     cin >> n; 
  42.     for(int i = 1; i <= n; i++) 
  43.     { 
  44.         cin >> x[i]; 
  45.     } 
  46.     for(int i = 1; i <= n; i++) 
  47.         cin >> cost[i]; 
  48.     for(int i = 1; i <= n; i++)
  49.     {
  50.     	vector <int> pFactors;
  51.     	int t = x[i];
  52.     	for(int j = 2; j*j <= t; j++)
  53.     		if(t % j == 0)
  54.     		{
  55.     			pFactors.push_back(j);
  56.     			while(t % j == 0)
  57.     				t /= j;
  58.     		}
  59.     	if(t > 1)
  60.     		pFactors.push_back(t);
  61.     	N = pFactors.size();
  62.  
  63.     	for(int j = 1; j <= n; j++)
  64.     	{
  65.     		m[j] = 0;
  66.     		for(int k = 0; k < N; k++)
  67.     			if(x[j] % pFactors[k] != 0)
  68.     				m[j] |= (1<<k);
  69.     	}
  70.     	memset(DP, 0xff, sizeof(DP));
  71.     	ans = min(ans, cost[i] + dp(1, 0));
  72.     }
  73.     if(ans == 1000000000) 
  74.         ans = -1; 
  75.     cout << ans << endl; 
  76.     return 0; 
  77. } 
  78.  
  79. int main() 
  80. { 
  81.     #ifdef LOCAL_TEST 
  82.         freopen("in.txt", "r", stdin); 
  83.         freopen("out.txt", "w", stdout); 
  84.     #endif 
  85.     ios :: sync_with_stdio(false); 
  86.     cout << fixed << setprecision(16); 
  87.     return MAIN(); 
  88. } 
  89.  
Success #stdin #stdout 0s 3884KB
comments (?)
stdin 
Standard input is empty
stdout 
-1
https://ideone.com/bxjvtX
language:
C++14 (gcc 8.3)
created:
9 years 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!