fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4. ll a[100000],r[100000],z[100000];
  5. ll n,k,heads;
  6. void addEdge(vector<vector<ll>>& adj,ll x,vector<bool>& visited);
  7. ll maxMoney(ll k,ll x);
  8. int main() {
  9. 	ios_base::sync_with_stdio(false);
  10. 	cin.tie(NULL);
  11. 	ll t,x;
  12. 	cin>>t;
  13. 	for(ll i=0;i<t;i++)
  14. 	{
  15. 	    cin>>n;
  16. 	    for(ll j=0;j<n;j++)
  17. 	    {
  18. 	        cin>>a[j];
  19. 	    }
  20. 	    cin>>k>>x;
  21. 	    cout<<maxMoney(k,x)<<"\n";
  22. 	}
  23. 	return 0;
  24. }
  25. ll maxMoney(ll k,ll x)
  26. {
  27.     for(ll i=0;i<n;i++)
  28. 	{
  29. 	   z[i]=(a[i]^x);
  30. 	}
  31.     if (n==k)
  32.     {
  33.         ll sum1=0,sum2=0;
  34.         for(ll i=0;i<n;i++)
  35.         {
  36.             sum1+=a[i];
  37.             sum2+=z[i];
  38.         }
  39.         if (sum1>sum2) return sum1;
  40.         return sum2;
  41.     }
  42.     ll b[n],sum=0;
  43.     heads=0;
  44.     for(ll i=0;i<n;i++)
  45.     {
  46.         b[i]=(z[i]-a[i]);
  47.         if(b[i]>0) heads++;
  48.     }
  49.     for(ll i=0;i<=n;i++)
  50.     {
  51.         r[i]=i;
  52.     }
  53. 	vector<vector<ll>> adj(n+1);
  54. 	vector<bool> visited(n+1,false);
  55.     addEdge(adj,heads,visited);
  56.     ll maxTails=n-r[heads];
  57.     for(ll i=0;i<n;i++)
  58.     {
  59.         if(z[i]<a[i]) a[i]=z[i];
  60.         sum+=a[i];
  61.     }
  62.     for(ll i=0;i<n;i++)
  63.     {
  64.         b[i]=abs(z[i]-a[i]);
  65.     }
  66.     sort(b,b+n,greater<int>());
  67.     for(ll i=0;i<maxTails;i++)
  68.     {
  69.         sum+=b[i];
  70.     }
  71.     return sum;
  72. }
  73. void addEdge(vector<vector<ll>>& adj,ll x,vector<bool>& visited)
  74. {
  75.     visited[x]=true;
  76.     if (r[x]<r[heads]) r[heads]=r[x];
  77.     else r[x]=r[heads];
  78.     for(ll j=0;j<=x;j++)
  79.     {
  80.     	if (j>k) break;
  81.     	if (k-j>n-x) continue;
  82.     	adj[x].push_back(x+k-2*j);
  83.     	if (visited[x+k-2*j]==false) addEdge(adj,x+k-2*j,visited);
  84.     }
  85. }
Success #stdin #stdout 0s 17584KB
comments (?)
stdin
copy 
5
5
1 2 3 4 5
2
4
7
10 15 20 13 2 1 44
4
14
5
12 45 23 87 2
3
5
1
5
1
4
4
84 56 87 58
3
1
stdout
copy 
19
95
156
5
287
https://ideone.com/F6FqVm
language:
C++ (gcc 8.3)
created:
4 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!