Submission #34289878

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

const int maxN = 200011;

struct Item {
  ll value, cost;

  Item advance_bit(int bit) {
    ll b = 1 << bit;

    if (value & b) 
      return *this;

    ll next = ((value >> bit) | 1) << bit;
    return {
      .value = next,
      .cost = cost + next - value
    };
  }

  bool operator<(const Item &other) const {
    return cost < other.cost;
  }
};

int n, k;
ll m, sol;
Item v[maxN], aux[maxN];

void decide_bit(int bit) {
  for (int i = 0; i < n; i++)
    aux[i] = v[i].advance_bit(bit);

  nth_element(aux, aux + k - 1, aux + n);
  ll total = 0;

  for (int i = 0; i < k; i++)
    total += aux[i].cost;

  if (total <= m) { 
    sol |= 1 << bit;
    memcpy(v, aux, sizeof(v));
  }
}

int main()
{

  cin >> n >> m >> k;
  for (int i = 0; i < n; i++) {
    cin >> v[i].value;
    v[i].cost = 0;
  }

  for (int bit = 31; bit >= 0; bit--)
    decide_bit(bit);
  
  cout << sol;


  return 0;
}

Submission Info

Judge Result