Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define SF(x) scanf("%I64d",&x)
- #define F first
- #define S second
- #define MEM(a,b) memset(a,b,sizeof(a))
- #define DB(x) cout << #x << " is " << x << endl
- #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.
- #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.
- #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.
- #define popcount(x) __builtin_popcount(x) // This function returns number of active bits in the binary represintation of the number
- #define pb push_back
- using namespace std;
- typedef long long ll;
- ll Mypow(ll X,ll Y){
- if(Y < 0)return 0;
- if(Y == 0)return 1;
- if(Y == 1){
- return X;
- }
- else{
- ll x = Mypow(X ,Y / 2);
- x *= x;
- if(Y % 2)
- return (x * X);
- else
- return x;
- }
- }
- int dp[5010][5010];
- int n, a[5010];
- pair < int, pair < int , int > > arr1[5010];
- int endd[5010];
- int start[5010];
- int k = 1;
- bool vis[5010];
- bool B[5010];
- int DP(int pos1, int pos2)
- {
- if(pos1 > k)
- return 0;
- int &cur = dp[pos1][pos2];
- if(cur != -1){
- return cur;
- }
- cur = DP(pos1 + 1, pos2);
- if(arr1[pos1].F > pos2){
- cur = max(cur, DP(pos1 + 1, arr1[pos1].S.F) + arr1[pos1].S.S);
- }
- return cur;
- }
- int main()
- {
- cin >> n;
- for(int i = 1 ; i <= n ; i++){
- cin >> a[i];
- }
- for(int i = n ; i > 0 ; i--){
- if(!vis[a[i]]){
- vis[a[i]] = true;
- endd[a[i]] = i;
- }
- }
- memset(vis, 0, sizeof(vis));
- for(int i = 1 ; i <= n ; i++){
- if(!vis[a[i]]){
- vis[a[i]] = true;
- start[a[i]] = i;
- }
- }
- memset(vis, 0, sizeof(vis));
- for(int i = 1 ; i <= n ; i++){
- if(start[a[i]] == i){
- int des = endd[a[i]];
- int j;
- for(j = i ; j <= des ; j++){
- des = max(des, endd[a[j]]);
- }
- j--;
- arr1[k].F = i;
- arr1[k].S.F = j;
- memset(B, 0, sizeof(B));
- for(int l = i ; l <= j ; l++){
- if(!B[a[l]]){
- B[a[l]] = true;
- arr1[k].S.S ^= a[l];
- }
- }
- k++;
- }
- }
- k--;
- sort(arr1 + 1, arr1 + k);
- memset(dp, -1, sizeof(dp));
- cout << DP(1, 0) << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement