fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define MOD 1000000007
  7. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  8. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  9. #define ALL(x) (x).begin(),(x).end()
  10. #define ii pair<int,int>
  11. #define iii pair<int,pair<int,int>>
  12. //const int MOD = 998244353;
  13. const int MAXN = 1e6+7;
  14. int a[MAXN],dp[MAXN],bit[MAXN];
  15. void update(int x,int val){
  16.     for (;x<=MAXN;x+=x&-x)bit[x] = max(bit[x],val);
  17. }
  18. int get(int x){
  19.     int ans = 0;
  20.     for (;x;x-=x&-x)ans = max(ans,bit[x]);
  21.     return ans;
  22. }
  23. bool prime(int x){
  24.     if (x == 2 || x == 3)return true;
  25.     if (x < 2 || x % 2 == 0 || x % 3 == 0)return false;
  26.     for (int i = 5;i <= (int)sqrt(x);i+=6)
  27.     if (x % i == 0 || x % (i + 2) == 0)return false;
  28.     return true;
  29. }
  30. int F(int x){
  31.     int ans = 1;
  32.     for (int i = 2;i*i*i <= x;i++)
  33.     if (x % i == 0){
  34.         int cnt = 1;
  35.         while(x % i == 0){
  36.             cnt++;
  37.             x = x / i;
  38.         }
  39.         ans = ans * cnt;
  40.     }
  41.     if (x <= 1)return ans;
  42.     int X = sqrt(x);
  43.     if (prime(x))ans = ans * 2;
  44.     else if (X*X == x && prime(X))ans = ans * 3;
  45.     else ans = ans * 4;
  46.     return ans;
  47. }
  48. int main(){
  49.     ios_base::sync_with_stdio(false);
  50.     cin.tie(0); cout.tie(0);
  51.     int n;cin >> n;
  52.     FOR(i,1,n)cin >> a[i];
  53.     FOR(i,1,n)a[i] = F(a[i]);
  54.     FOR(i,1,n){
  55.         dp[i] = get(a[i])+1;
  56.         update(a[i]+1,dp[i]);
  57.         dp[i] = max(dp[i],dp[i-1]);
  58.     }
  59.     cout << dp[n];
  60.     return (0^0);
  61. }
  62. /*   /\_/\
  63.     (  -.-)
  64.     / >  \>
  65. */
Success #stdin #stdout 0s 5832KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/UvYiYl
language:
C++ (gcc 8.3)
created:
8 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!