General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
93587741 Practice:
mehulcoder
811C - 32 C++17 (GCC 7-32) Accepted 31 ms 452 KB 2020-09-23 21:08:49 2020-09-23 21:08:50
→ Source
/*
Author: Mehul Chaturvedi
Talent is overrated
*/

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define vll vector<long long>
#define vset(v, n, val) v.clear(); v.resize(n, val)
#define rep(i, n) for (int i = 0, _n = (n); i < _n; i++)
#define trav(a, x) for(auto& a : x)

/*
* Beautiful question <3
* Basically dp[i]---> Best answer of the "Total array"
* if you choose only segments till i, and endpoint of the
* last segment is at i(check if that is even possible).
* Check if the rightmost element same as a[i] is at i
* and not after i, if it is after i then we cannot take make
* a segment end at i. Therefore in this case dp[i] = dp[i-1]
* else the dp[i] ---> max(dp[i-1], dp[k-1]+XOR(a[k]--->a[i]))
* where k is the extended(due to the possible 'lefter' lefts)
* left of the segment ending at i.
*/


vll a, dp;
vll leftt(5005, -1), rightt(5005, -1);
ll get(ll end) {
	if (end < 0) return 0;

	ll &ans = dp[end];
	if (ans != -1) return ans;

	if (end != rightt[a[end]]) return ans = get(end - 1);
	else {

		ll currLeft = leftt[a[end]];
		ll currRight = end;
		ll i = currRight;
		set<ll> temp;
		while (i > currLeft) {
			temp.insert(a[i]);
			if (rightt[a[i]] > currRight) return ans = get(end - 1);
			i--;
			currLeft = min(currLeft, leftt[a[i]]);
		}
		temp.insert(a[i]);
		ll val = 0;
		trav(elem, temp) {
			val = val ^ elem;
		}
		return ans = max(get(i - 1) + val, get(end - 1));
	}

}

void solve() {
	ll n; cin >> n;
	vset(a, n, 0);
	vset(dp, n, -1);

	rep(i, n) cin >> a[i];

	rep(i, n) {
		if (leftt[a[i]] == -1) {
			leftt[a[i]] = i;
			rightt[a[i]] = i;
		} else {
			rightt[a[i]] = i;
		}
	}

	rep(i, n) {
		get(i);
	}
	cout << *max_element(all(dp)) << '\n';

	return;
}

int main(int argc , char ** argv) {
	ios_base::sync_with_stdio(false) ;
	cin.tie(NULL) ;

	ll t = 1;

	while (t--) {
		solve();
	}

	return 0 ;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details