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. typedef tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
  6. s.find_by_order(x) xth element in set
  7. x.order_of_key(x) number of elements <x*/
  8. #define ll long long
  9. #define vi vector<int>
  10. #define si set<int>
  11. #define mii map<int,int>
  12. #define pb push_back
  13. #define pf push_front
  14. #define PI acos(-1)
  15. #define pii pair<int,int>
  16. #define extract_word(s)  stringstream str(s); while(str>>word)
  17. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  18. #define SET(s) cout<<fixed<<setprecision(s)
  19. #define set0(a) memset(a,0,sizeof(a))
  20. #define endl "\n"
  21. #define all(a) a.begin(),a.end()
  22. #define rall(a) a.rbegin(),a.rend()
  23. #define lower_string(s) transform(all(s),s.begin(),::tolower)
  24. #define upper_string(s) transform(all(s),s.begin(),::toupper)
  25. #define len(s) (int)s.size()
  26. #define F first
  27. #define S second
  28. template<typename T,typename U>
  29. bool compare(T x,U y){return(abs(x-y)<=1e-9);}
  30. const int MOD=1e9+7;
  31. void solve()
  32. {
  33. int n;
  34. cin>>n;
  35. int a[n];
  36. for(auto &x:a)
  37. cin>>x;
  38. vector<vi>dp(n,vi(3));
  39. dp[0][0]=a[0],dp[0][1]=a[0]-1,dp[0][2]=a[0]+1;
  40. for(int i=1;i<n;i++)
  41. {
  42. 	dp[i][0]=max({__gcd(dp[i-1][0],a[i]),__gcd(dp[i-1][1],a[i]),__gcd(dp[i-1][2],a[i])});
  43. 	dp[i][1]=max({__gcd(dp[i-1][0],a[i]-1),__gcd(dp[i-1][1],a[i]-1),__gcd(dp[i-1][2],a[i]-1)});
  44. 	dp[i][2]=max({__gcd(dp[i-1][0],a[i]+1),__gcd(dp[i-1][1],a[i]+1),__gcd(dp[i-1][2],a[i]+1)});
  45. }
  46. cout<<max({dp[n-1][0],dp[n-1][1],dp[n-1][2]});
  47. }
  48. int main()
  49. {
  50. //code
  51. fastio
  52. int t=1;
  53. cin>>t;
  54. while(t--)
  55. {
  56. solve();
  57. cout<<endl;
  58. }
  59. }
  60.  
Time limit exceeded #stdin #stdout 5s 4896KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/D4eCUM
language:
C++14 (gcc 8.3)
created:
3 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!