fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. using namespace __gnu_pbds;
  5. #pragma GCC optimize("O3,unroll-loops")
  6. #ifdef LOCAL
  7. #include "debug.h"
  8. #else
  9. #define dbg(...)
  10. #endif
  11. #define endl '\n'
  12. #define int int64_t
  13. const long long mod = 1000000007, MaxN = 200005, INF = 1e10;
  14. const int MAX = 1e5 + 5;
  15. template <typename T>
  16. struct BIT
  17. {
  18. 	int sz;
  19. 	vector<T> tree;
  20. 	BIT() {};
  21. 	BIT(int N)
  22. 	{
  23. 		sz = N + 1;
  24. 		tree.resize(sz, -INF);
  25. 	}
  26. 	int lsb(int x)
  27. 	{
  28. 		return (x & -x);
  29. 	}
  30. 	void update(int idx, T x)
  31. 	{
  32. 		for (; idx < sz; idx += lsb(idx))
  33. 			tree[idx] = max(x, tree[idx]);
  34. 	}
  35. 	T get(int idx)
  36. 	{
  37. 		T Max = -INF;
  38. 		for (; idx; idx -= lsb(idx)){
  39. 			Max = max(Max, tree[idx]);
  40. 		}
  41. 		return Max;
  42. 	}
  43.  
  44. };
  45. vector<BIT<int>>all(MAX);
  46. vector<vector<int>>fact(MAX);
  47. void solve()
  48. {
  49. 	int N;
  50. 	cin >> N;
  51. 	vector<int> a(N + 1);
  52. 	for (int i = 1; i <= N; i++)
  53. 	{
  54. 		cin >> a[i];		
  55. 	}
  56. 	vector<int>dp(N + 1);
  57. 	for (int i = 1; i <= MAX; i++)
  58. 	{
  59. 		//bit[x][i] = max dp value where a[j] is divisble by x and a[j] <= i*x
  60. 		all[i] = BIT<int>(MAX / i + 3);
  61. 	}
  62. 	for (int i = 1; i <= N; i++)
  63. 	{
  64. 		for (auto &x : fact[a[i]])
  65. 		{
  66. 			//index of a[i] in the compressed form
  67. 			int idx = a[i] / x + 1;
  68. 			int y = all[x].get(idx);
  69. 			dp[i] = max(dp[i], y + x);
  70. 		}
  71. 		for(auto x : fact[a[i]]){
  72. 			int idx = a[i] / x + 1;
  73. 			//update the dp values with the new dp[i]
  74. 			all[x].update(idx, dp[i]);
  75. 		}
  76. 	}
  77. 	cout << *max_element(dp.begin(), dp.end()) << endl;
  78. }
  79. signed main()
  80. {
  81. 	// freopen("mootube.in","r",stdin);
  82. 	// freopen("mootube.out","w",stdout);
  83. 	#ifdef LOCAL
  84. 	FileRedirect("test");
  85. 	#endif
  86. 	ios::sync_with_stdio(0);
  87. 	cin.tie(nullptr);
  88. 	cout.tie(nullptr);
  89. 	//precompute factors
  90. 	for(int i = 1;i < MAX;i++){
  91. 		for(int j = i;j < MAX;j += i){
  92. 			fact[j].push_back(i);
  93. 		}
  94. 	}	
  95. 	int Tc = 1;
  96. 	cin >> Tc;
  97. 	for (int T = 1; T <= Tc; T++)
  98. 		solve();
  99. }
Success #stdin #stdout 0.11s 36524KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/oYrkBF
language:
C++ 4.3.2 (gcc-4.3.2)
created:
11 days 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!