fork download
copy 
  1. //not-my-source-code
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. using namespace std;
  6.  
  7. const int N=5010;
  8. int f[N][N],minN[N][N],maxN[N][N],last[N];
  9. int n,q,a[N];
  10.  
  11. void work()
  12. {
  13. 	int i,j,k,ii,jj;
  14. 	for (i=1;i<=n;i++)
  15. 	{
  16. 		f[i][i]=1;
  17. 		last[i]=i;
  18. 		minN[i][i]=maxN[i][i]=a[i];
  19. 		for (j=i+1;j<=n;j++)
  20. 		{
  21. 			minN[i][j]=min(minN[i][j-1],a[j]);
  22. 			maxN[i][j]=max(maxN[i][j-1],a[j]);
  23. 		}
  24. 	}
  25. 	for (k=2;k<=n;k++)
  26. 		for (i=1;i<=n-k+1;i++)
  27. 		{
  28. 			j=i+k-1;
  29. 			if (maxN[i][j]-minN[i][j]!=j-i)
  30. 				f[i][j]=0;
  31. 			else
  32. 			{
  33. 				if (minN[i][j]<minN[i][last[i]])f[i][j]=1;
  34. 				else
  35. 					f[i][j]=f[i][last[i]]+f[last[i]+1][j];
  36. 				last[i]=j;
  37. 			}
  38. 		}
  39. 	int ans=f[1][n];
  40. 	for (i=1;i<=n;i++)
  41. 		for (j=i;j<=n;j++)
  42. 			if (f[i][j]&&(i==1||f[1][i-1]&&minN[1][i-1]==1))
  43. 			{
  44. 				jj=maxN[i][j];
  45. 				if (jj==n||maxN[jj+1][n]==n&&f[jj+1][n])
  46. 					for (ii=jj;ii>j;ii--)
  47. 						if (f[ii][jj]&&minN[ii][jj]==i)
  48. 							ans=max(ans,f[1][i-1]+f[j+1][ii-1]+f[jj+1][n]+2);
  49. 			}
  50. 	cout<<ans<<endl;
  51. }
  52.  
  53. int main()
  54. {
  55. 	int T,i,j;
  56. 	cin>>T;
  57. 	for (i=1;i<=T;i++)
  58. 	{
  59. 		cin>>n>>q;
  60. 		for (j=1;j<=n;j++)cin>>a[j];
  61. 		printf("Case #%d: ",i);
  62. 		work();
  63. 	}
  64. 	return 0;
  65. }
  66.  
Success #stdin #stdout 0s 297664KB
comments (?)
stdin
copy 
0 0
stdout
copy 
Standard output is empty
https://ideone.com/AQo37e
my template :)
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!