Advertisement
Md_Ahad

HSTU Contest E

Jul 1st, 2025
340
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. const ll N = 2e5+7;
  6. vector<ll> divisor[N];
  7. ll dp[N];
  8.  
  9. signed main() {
  10.     ios_base::sync_with_stdio(0); cin.tie(0);
  11.     int tc; cin >> tc;
  12.  
  13.     for (ll i = 1; i < N; i++) {
  14.         for (ll j = i; j < N; j += i) divisor[j].push_back(i);
  15.     }
  16.  
  17.     test:
  18.     while (tc--) {
  19.         ll n; cin >> n;
  20.        
  21.         ll arr[n];
  22.         for (auto &u : arr) {
  23.             cin >> u;
  24.             for (auto &v : divisor[u]) dp[v] = 0;
  25.         }
  26.        
  27.         for (ll i = n-1; i >= 0; i--) {
  28.             ll d = (divisor[arr[i]].size()+2) / 3;
  29.             ll ans = arr[i];
  30.             for (auto &u : divisor[arr[i]]) {
  31.                 if (divisor[u].size() >= d) ans = max(ans, dp[u]+arr[i]);
  32.             }
  33.             for (auto &u : divisor[arr[i]]) dp[u] = max(dp[u], ans);
  34.         }
  35.  
  36.         cout << dp[1] << "\n";
  37.     }
  38. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement