fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. //#define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e9
  16. const int N = 1e5 + 5;
  17. int n;
  18. vector<int>v,temp;
  19. int dp[N];
  20. int solve(int i,int j)
  21. {
  22.   if(i==n) return 0;
  23.   int t=0,l=0;
  24.   int &ret=dp[j];
  25.   if(ret!=-1) 
  26.   return ret;
  27.   if(j==100003) 
  28.   {
  29.   t=solve(i+1,i)+1;
  30.   l=solve(i+1,j);
  31.   }
  32.   else
  33.   {
  34.   if(__gcd(temp[i],temp[j])!=1)
  35.   t=solve(i+1,i)+1;
  36.   l=solve(i+1,j);
  37.   }
  38.   return ret=max(t,l);
  39. }
  40. void HereWeGoAgain()
  41. {
  42.    cin>>n;
  43.    v.resize(n);
  44.    dpp(dp,-1);
  45.    for(int i=0;i<n;i++) cin>>v[i];
  46.    for(int i=0;i<v.size();i++)
  47.    {
  48.      auto it=lower_bound(all(temp),v[i]);
  49.      if(it==temp.end())
  50.       temp.push_back(v[i]);
  51.       else
  52.       *it=v[i];
  53.    }
  54.    cout<<solve(0,100003)<<el;
  55. }
  56. int32_t main() 
  57. {
  58.     Arwa
  59.     int t=1;
  60.     //cin>>t;
  61.     for(int i=1;i<=t;i++)
  62.     {
  63.     HereWeGoAgain();
  64.     }
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/pt6ggv
language:
C++ (gcc 8.3)
created:
1 day 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!