Guest User

Untitled

a guest
May 27th, 2017
359
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define SF(x) scanf("%I64d",&x)
  3. #define F first
  4. #define S second
  5. #define MEM(a,b) memset(a,b,sizeof(a))
  6. #define DB(x) cout << #x << " is " << x << endl
  7. #define ffs(x) __builtin_ffs(x) // This function returns 1 + least significant 1-bit of x. If x == 0, returns 0. Here x is int, this function with suffix 'l' gets a long argument and with suffix 'll' gets a long long argument.
  8. #define clz(x) __builtin_clz(x) // This function returns number of leading 0-bits of x which starts from most significant bit position. x is unsigned int and like previous function this function with suffix 'l gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
  9. #define ctz(x) __builtin_ctz(x) // This function returns number of trailing 0-bits of x which starts from least significant bit position. x is unsigned int and like previous function this function with suffix 'l' gets a unsigned long argument and with suffix 'll' gets a unsigned long long argument. If x == 0, returns an undefined value.
  10. #define popcount(x) __builtin_popcount(x) // This function returns number of active bits in the binary represintation of the number
  11. #define pb push_back
  12.  
  13. using namespace std;
  14. typedef long long ll;
  15.  
  16. ll Mypow(ll X,ll Y){
  17. if(Y < 0)return 0;
  18. if(Y == 0)return 1;
  19. if(Y == 1){
  20. return X;
  21. }
  22. else{
  23. ll x = Mypow(X ,Y / 2);
  24. x *= x;
  25. if(Y % 2)
  26. return (x * X);
  27. else
  28. return x;
  29. }
  30. }
  31.  
  32. int dp[5010][5010];
  33. int n, a[5010];
  34. pair < int, pair < int , int > > arr1[5010];
  35. int endd[5010];
  36. int start[5010];
  37. int k = 1;
  38. bool vis[5010];
  39. bool B[5010];
  40.  
  41. int DP(int pos1, int pos2)
  42. {
  43. if(pos1 > k)
  44. return 0;
  45. int &cur = dp[pos1][pos2];
  46. if(cur != -1){
  47. return cur;
  48. }
  49. cur = DP(pos1 + 1, pos2);
  50. if(arr1[pos1].F > pos2){
  51. cur = max(cur, DP(pos1 + 1, arr1[pos1].S.F) + arr1[pos1].S.S);
  52. }
  53. return cur;
  54. }
  55.  
  56. int main()
  57. {
  58. cin >> n;
  59. for(int i = 1 ; i <= n ; i++){
  60. cin >> a[i];
  61. }
  62. for(int i = n ; i > 0 ; i--){
  63. if(!vis[a[i]]){
  64. vis[a[i]] = true;
  65. endd[a[i]] = i;
  66. }
  67. }
  68. memset(vis, 0, sizeof(vis));
  69. for(int i = 1 ; i <= n ; i++){
  70. if(!vis[a[i]]){
  71. vis[a[i]] = true;
  72. start[a[i]] = i;
  73. }
  74. }
  75. memset(vis, 0, sizeof(vis));
  76. for(int i = 1 ; i <= n ; i++){
  77. if(start[a[i]] == i){
  78. int des = endd[a[i]];
  79. int j;
  80. for(j = i ; j <= des ; j++){
  81. des = max(des, endd[a[j]]);
  82. }
  83. j--;
  84. arr1[k].F = i;
  85. arr1[k].S.F = j;
  86. memset(B, 0, sizeof(B));
  87. for(int l = i ; l <= j ; l++){
  88. if(!B[a[l]]){
  89. B[a[l]] = true;
  90. arr1[k].S.S ^= a[l];
  91. }
  92. }
  93. k++;
  94. }
  95. }
  96. k--;
  97. sort(arr1 + 1, arr1 + k);
  98. memset(dp, -1, sizeof(dp));
  99. cout << DP(1, 0) << endl;
  100. return 0;
  101. }
RAW Paste Data