Submission #34171218

---

Source Code Expand

// Problem: B - Plus and AND
// Contest: AtCoder - AtCoder Regular Contest 146
// URL: https://atcoder.jp/contests/arc146/tasks/arc146_b
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
typedef long long ll;
#define rep(i, a, b) for(int i = (a); i <= (b); i ++)
#define per(i, a, b) for(int i = (a); i >= (b); i --)
#define Ede(i, u) for(int i = head[u]; i; i = e[i].nxt)
using namespace std;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? - 1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

const int N = 2e5 + 10;
int n, m, k, a[N], b[N], p[N], c[N];

ll check(int o) {
	rep(i, 1, n) {
		p[i] = i;
		if(a[i] >> o & 1) b[i] = 0;
		else b[i] = (1 << o) - (a[i] & ((1 << o) - 1));
	}
	sort(p + 1, p + n + 1, [](int x, int y) {return b[x] < b[y];});
	ll cur = 0;
	rep(i, 1, k) cur += b[p[i]];
	return cur;
}

void prework() {
	int lim = m;
	per(o, 30, 0) {
		ll ned = check(o);
		if(ned > lim) continue;
		if(ned) {rep(i, 1, k) c[i] = a[p[i]]; return;}
		lim -= ned;
		while(n && b[p[n]]) n --;
		rep(i, 1, n) b[i] = a[p[i]];
		rep(i, 1, n) a[i] = b[i];
	}
	rep(i, 1, k) c[i] = a[i];
}

bool solve(int o) {
	ll cur = 0;
	rep(i, 1, k) {
		if(c[i] >> o & 1) ;
		else cur += (1 << o) - (c[i] & ((1 << o) - 1));
	}
	if(cur > m) return false;
	m -= cur;
	rep(i, 1, k) if(c[i] >> o & 1) ; else c[i] = 0;
	return true;
}

int main() {
	n = read(), m = read(), k = read();
	rep(i, 1, n) a[i] = read();
	prework();
	int ans = 0;	
	per(o, 30, 0) if(solve(o)) ans |= (1 << o);
	printf("%d\n", ans);
	return 0;
}

Submission Info

Judge Result