fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long lint;
  4. typedef pair<int, int> pi;
  5.  
  6. int cost[1000005];
  7. int n, m, l[1005], a[1005], b[1005];
  8. int dp[20][1000005];
  9.  
  10. void solve(){
  11. 	memset(dp, 0x3f, sizeof(dp));
  12. 	dp[0][1] = 0;
  13. 	for(int i=1; i<20; i++){
  14. 		for(int j=(1<<(i-1)); j<=500000; j++){
  15. 			int p = 2;
  16. 			for(int k=2*j; k<=1000000; k+=j){
  17. 				dp[i][k] = min(dp[i][k], dp[i-1][j] + cost[p++]);
  18. 			}
  19. 		}
  20. 	}
  21. }
  22.  
  23. struct cht{
  24. 	int s, e;
  25. 	pi a[1005];
  26. 	void clear(){ s = e = 0;}
  27. 	void add(pi v){
  28. 		if(s < e && a[e-1].first == v.first){
  29. 			if(v.second >= a[e-1].second) return;
  30. 			else e--;
  31. 		}
  32. 		a[e] = v;
  33. 		while(e - 2 >= s && 
  34. 			1ll * (a[e-2].second - a[e-1].second) * (a[e].first - a[e-1].first) <=
  35. 			1ll * (a[e-1].second - a[e].second) * (a[e-1].first - a[e-2].first)){
  36. 			a[e-1] = a[e];
  37. 			e--;
  38. 		}
  39. 		e++;
  40. 	}
  41. 	int query(int x){
  42. 		if(e == 0) return 2e9;
  43. 		while(e - 2 >= s && a[e-2].first * x + a[e-2].second <= a[e-1].first * x + a[e-1].second) e--;
  44. 		return a[e-1].first * x + a[e-1].second;
  45. 	}
  46. }cht[20];
  47.  
  48. lint query(int s, int e){
  49. 	for(int i=0; i<20; i++) cht[i].clear();
  50. 	for(int i=0; i<m; i++){
  51. 		if(a[i] % e == 0 && s % a[i] == 0){
  52. 			for(int j=19; j>=0; j--){
  53. 				lint av = 2e9;
  54. 				for(int k=0; k<=j; k++){
  55. 					lint sum = dp[j-k][a[i] / e] + dp[k][s / a[i]];
  56. 					av = min(av, sum);
  57. 				}
  58. 				if(av < 1e9){
  59. 					pi w(b[i], (int)av - b[i] * j);
  60. 					for(int k=j; k<20; k++){
  61. 						cht[k].add(w);
  62. 					}
  63. 				}
  64. 			}
  65. 		}
  66. 	}
  67. 	lint ret = 0;
  68. 	for(int i=0; i<n; i++){
  69. 		int ans = cht[min(l[i], 19)].query(l[i]);
  70. 		if(l[i] < 20) ans = min(ans, dp[l[i]][s/e]);
  71. 		if(ans > 1e8) ans = -1;
  72. 		ret += ans;
  73. 	}
  74. 	return ret;
  75. }
  76.  
  77. int main(){
  78. 	int t, tmp[10005] = {};
  79. 	scanf("%d",&t);
  80. 	for(int i=1; i<=t; i++) scanf("%d",&tmp[i]);
  81. 	for(int i=1; i<=1000000; i++){
  82. 		for(int j=i; j<=1000000; j+=i){
  83. 			cost[j]++;
  84. 		}
  85. 	}
  86. 	for(int i=1; i<=1000000; i++) cost[i] = tmp[cost[i]];
  87. 	scanf("%d",&n);
  88. 	for(int i=0; i<n; i++) scanf("%d",&l[i]);
  89. 	sort(l, l+n);
  90. 	scanf("%d",&m);
  91. 	vector<pi> v;
  92. 	for(int i=0; i<m; i++) scanf("%d %d",&a[i],&b[i]);
  93. 	for(int i=0; i<m; i++) v.push_back(pi(b[i], a[i]));
  94. 	sort(v.begin(), v.end());
  95. 	for(int i=0; i<m; i++){
  96. 		b[i] = v[i].first, a[i] = v[i].second;
  97. 	}
  98. 	solve();
  99. 	int q; scanf("%d",&q);
  100. 	while(q--){
  101. 		int a, b;
  102. 		scanf("%d %d",&a,&b);
  103. 		if(a % b != 0) printf("%d\n", -n);
  104. 		else printf("%lld\n", query(a, b));
  105. 	}
  106. }
  107.  
Success #stdin #stdout 0.28s 85696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mBCCJP
language:
C++14 (gcc 8.3)
created:
7 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!