提出 #67002716

---

ソースコード 拡げる

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

#ifdef DEBUG
const int debug = 1;
#else
const int debug = 0;
#endif

typedef long long int ll;
typedef pair<ll, ll> P;
using mint = atcoder::modint998244353;
const ll FOD = 998244353;

const ll INF = 1'000'000'000'000'000'009LL;

#define rep(I, N) for (ll I = 0; I < (ll)(N); I++)

ll n, k, m, q, h, w;
vector<ll> a, b, c;


ll mygcd (ll l, ll r) {
	if (r == 0) return l;
	return mygcd(r, l % r);
}


vector<mint> frac, invf;
void f_init (ll n) {
	frac.resize(n+1);
	invf.resize(n+1);

	frac[0] = 1;
	for (ll i = 1; i <= n; i++) {
		frac[i] = frac[i-1] * i;
	}
	invf[n] = 1 / frac[n];
	for (ll i = n; i >= 1; i--) {
		invf[i-1] = invf[i] * i;
	}
}
mint ncr (ll n, ll r) {
	if (n < r || n < 0 || r < 0) return 0;
	return frac[n] * invf[r] * invf[n-r];
}
mint put (ll ball, ll bucket) {
	return ncr(ball + bucket - 1, ball);
}





const ll BITS = 61;

void solve () {
	vector<vector<ll> > y(BITS);
	rep (i, n) {
		y[a[i]].push_back(+b[i]);
	}
	ll curr = w;
	ll ans = 0;
	rep (i, BITS) {
		sort(y[i].begin(), y[i].end());

		if (curr % 2) {
			if (y[i].size() >= 1) {
				ans += y[i][y[i].size()-1];
				y[i].pop_back();

				curr--;
			}
		}

		if (i+1 < BITS) {
			ll j = y[i].size()-1;
			while (j >= 0) {
				y[i+1].push_back(y[i][j] + ((j-1 >= 0) ? y[i][j-1] : 0));
				j -= 2;
			}

			curr /= 2;
		}
	}

	cout << ans << "\n";
	return;
}



int main (void) {
	if (!debug) {
		std::cin.tie(nullptr);
		std::ios_base::sync_with_stdio(false);
	}

	int T;
	cin >> T;
	while (T--) {
		cin >> n >> w;
		a.resize(n);
		b.resize(n);
		rep (i, n) {
			cin >> a[i] >> b[i];
		}

		solve();
	}
	

	return 0;
}

提出情報

ジャッジ結果