fork download
copy 
  1. #include<iostream>
  2.  
  3.  
  4. using namespace std;
  5.  
  6.  
  7. static int lt[5001],rt[5001],cnt[5001];
  8. int main()
  9. {
  10. 	int n;
  11. 	cin >>n;
  12. 	int A[n];
  13. 	fill(lt,lt+5001,-1);
  14. 	fill(rt,rt+5001,-1);
  15. 	for(int i=0;i<n;i++)
  16. 	{
  17. 		cin >>A[i];
  18. 		if(lt[A[i]]==-1)
  19. 			lt[A[i]]=i;
  20. 		cnt[A[i]]++;
  21. 	}
  22. 	for(int i=n-1;i>=0;i--)
  23. 		if(rt[A[i]]==-1)
  24. 			rt[A[i]]=i;
  25.  
  26. 	int dp[n];
  27. 	dp[0]=0;
  28. 	if(rt[A[0]]==0)
  29. 		dp[0]=A[0];
  30. 	int count[5000];
  31.  
  32. 	for(int i=1;i<n;i++)
  33. 	{
  34. 		fill(count,count+5000,0);
  35. 		bool poss=true;
  36. 		int xors=0;
  37. 		for(int j=i;j>=lt[A[i]];j--)
  38. 		{
  39. 			if(not(rt[A[j]]<=i and lt[A[j]]>=lt[A[i]]))
  40. 				poss=false;
  41.  
  42. 			if(count[A[j]]==0)
  43. 				xors^=A[j];
  44. 			count[A[j]]++;
  45. 		}
  46. 		dp[i]=dp[i-1];
  47. 		if (poss==true)
  48. 		{
  49. 			dp[i]=max(dp[lt[A[i]]-1] + xors,dp[i-1]);
  50. 		}
  51. 		//cout<<dp[i]<<" ";
  52.  
  53. 	}
  54. 	//cout<<endl;
  55. 	cout<<dp[n-1];
  56. }
Success #stdin #stdout 0s 15280KB
comments (?)
stdin
copy 
6
4 4 2 5 2 3
stdout
copy 
14
https://ideone.com/O4ctPB
language:
C++14 (gcc 8.3)
created:
6 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!