fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define dbg1(x)     cerr<<#x<<':'<<x<<'\n'
  3. #define dbg2(x,y)   cerr<<#x<<':'<<x<<','<<#y<<':'<<y<<'\n'
  4. #define dbg3(x,y,z) cerr<<#x<<':'<<x<<','<<#y<<':'<<y<<','<<#z<<':'<<z<<'\n'
  5. using namespace std;
  6. typedef long long ll;
  7.  
  8. template <class T>  /// <--- layering the gcd
  9. T gcd(T a,T b){
  10.   if(a == 0 or b == 0) return 0;
  11.   return __gcd(a,b);
  12. }
  13.  
  14. const int N = 350;
  15. int n,m,x,y;
  16. int seq[N];
  17.  
  18. ll cache[N][N][2];
  19. bool vis[N][N][2];
  20.  
  21. ll dp(int l,int rem,int end){
  22.   ll &ans = cache[l][rem][end];
  23.   if(vis[l][rem][end]) return ans;
  24.   ans = 0;
  25.   vis[l][rem][end] = true;
  26.   /// base cases check order
  27.  
  28.  
  29.   ll num = 0;
  30.  
  31.   if(l >= n) return 0; /// if the last separator was placed at the end of the array
  32.  
  33.   if(end){ /// if we can end the array here
  34.   	int digits = n-l;  /// number of digits remaining
  35.   	if(digits == 0 or digits > m) return 0;
  36.   	for(int i=1;i<=digits;i++) /// calculate the remaining number
  37.   	  num = num*10 + seq[l+i];
  38.   	ans = num;
  39.   	//dbg3(l,rem,end);
  40. 	//dbg1(ans);
  41. 	return ans;
  42.   }
  43.  
  44.   for(int i=1;i<=m and l+i<=n ;i++) /// while reading m digits till end of array
  45.     {
  46.       num = num*10 + seq[l+i];
  47.       ans = max(ans , gcd(num,dp(l+i,rem-1,(rem-1) == 0)));  /// place separator at l+i position, dec. rem,if rem becomes zero terminate
  48.  
  49.       if(y-x >= rem-1)            /// if we already have used x separators
  50.       ans = max(ans,gcd(num,dp(l+i,rem-1,1))); /// place separator at l+i position at terminate the sequence with end = 1
  51.  
  52.   }
  53.   return ans;
  54. }
  55.  
  56.  
  57. int main(){
  58.  
  59. //  freopen("in.txt","r",stdin);
  60. //  freopen("err.txt","w",stderr);
  61.   string str;
  62.   int t; cin>>t;
  63.   while(t--){
  64.     memset(vis,0,sizeof vis);
  65.     cin>>n; // size of seq.
  66.     cin>>str;
  67.  
  68.     for(int i=0;i<(int)str.size();i++)
  69.       seq[i+1] = str[i]-'0';
  70.  
  71.     cin>>m>>x>>y;
  72.     ll ans = dp(0,y,0);
  73.  
  74. 	cout<<ans<<'\n';
  75.  }
  76.  
  77. }
  78.  
Success #stdin #stdout 0s 5628KB
comments (?)
stdin
copy 
2
3
474
2 1 1
34
6311861109697810998905373107116111
10 4 25
stdout
copy 
2
1
https://ideone.com/uCWbqv
language:
C++14 (gcc 8.3)
created:
7 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!