There are two friends X and Y . In one turn,X chooses any of the element. Y chooses the median of the elements left.
This way only (N/2) turns are possible.
Greedy approaches of mine failed in hidden cases but ran on the smaple test cases only do help please
sample test cases:
3
1 2 3 4
ans 7
4
5 10 15 5
ans 20
The code i wrote :
ll n;
cin>>n;
vector<ll> a(n);
for(auto &ele:a)
cin>>ele;
ll i = n/2-1,j=n/2;sum=0;
while(i>=0){
sum += max(a[j++],a[i--]);
}
cout<<sum;