Submission #67630246

---

Source Code Expand

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

#define int ll
#define fast_io cin.tie(0)->sync_with_stdio(0);
#define endl '\n'
typedef long long ll;

const int INF = 1e18;

vector<int> maxplus(vector<int>& a, vector<int>& b) {
	int n = a.size(), m = b.size();
	vector<int> ans(n + m - 1);

	int i = 0, j = 0;
	while (i < n - 1 || j < m - 1) {
		if (i == n - 1) {
			j++;
		} else if (j == m - 1) {
			i++;
		} else {
			if (a[i + 1] + b[j] > a[i] + b[j + 1]) {
				i++;
			} else {
				j++;
			}
		}
		ans[i + j] = max(-INF, a[i] + b[j]);
	}

	//cout << "conv" << endl;
	//for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
	//cout << endl;
	//for (int i = 0; i < b.size(); i++) cout << b[i] << " ";
	//cout << endl;
	//for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";
	//cout << endl;
	
	return ans;
}

int32_t main() {
	fast_io;

	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		int w; cin >> w;

		const int MX = __lg(w) + 1;
		vector<vector<int>> items(MX);

		for (int i = 0; i < n; i++) {
			int x, y; cin >> x >> y;
			if (x < MX) items[x].push_back(y);
		}

		vector<int> dp(n + 1, -INF);
		dp[0] = 0;
		for (int x = 0; x < MX; x++) {
			sort(items[x].rbegin(), items[x].rend());
			for (int i = 1; i < (int)items[x].size(); i++) items[x][i] += items[x][i - 1];
			items[x].insert(items[x].begin(), 0);

			auto ndp = maxplus(dp, items[x]);

			for (int i = 0; i < ndp.size(); i++) {
				if (w >> x & 1) {
					dp[i/2] = max(dp[i/2], ndp[i]);
				} else {
					dp[(i + 1)/2] = max(dp[(i + 1)/2], ndp[i]);
				}
			}
		}

		cout << dp[0] << endl;
	}
}

Submission Info

Compile Error

Main.cpp: In function ‘int32_t main()’:
Main.cpp:67:43: warning: comparison of integer expressions of different signedness: ‘ll’ {aka ‘long long int’} and ‘std::vector<long long int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   67 |                         for (int i = 0; i < ndp.size(); i++) {
      |                                         ~~^~~~~~~~~~~~

Judge Result