AOJ0613 財宝 (Treasures)

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0613

解法

半分全列挙した後にスライド最小値(小とは言っていない)

実装

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

#define int long long

const int MAX_N = 30;

int N, D;

struct Treasure
{
	int x, y;
	Treasure() { x = y = 0; }
	Treasure(int _x, int _y) { x = _x; y = _y; }
	Treasure operator + (const Treasure &t) const
	{
		return Treasure(x + t.x, y + t.y);
	}
	Treasure operator - (const Treasure &t) const
	{
		return Treasure(x - t.x, y - t.y);
	}
	bool operator < (const Treasure &d) const
	{
		return x < d.x;
	}
};

Treasure treasure[MAX_N];

void DFS(int l, int r, Treasure sum, vector<Treasure> &res)
{
	if (l == r)
	{
		res.push_back(sum);
		return;
	}
	DFS(l + 1, r, sum, res);
	DFS(l + 1, r, sum + treasure[l], res);
	DFS(l + 1, r, sum - treasure[l], res);
}

int sum[20000000];

signed main()
{
	cin >> N >> D;
	for (int i = 0; i < N; i++)
	{
		cin >> treasure[i].x >> treasure[i].y;
	}
	vector<Treasure> s, t;
	s.reserve(20000000); t.reserve(20000000);
	DFS(0, N / 2, Treasure(), s);
	DFS(N / 2, N, Treasure(), t);
	sort(s.begin(), s.end());
	sort(t.begin(), t.end());
	int ans = -LLONG_MAX;
	{
		int l = 0, r = 0;
		deque<int> dq;
		for (int i = t.size() - 1; i >= 0; i--)
		{
			while (r < s.size() && s[r].x + t[i].x <= D)
			{
				while (!dq.empty() && s[dq.back()].y <= s[r].y) dq.pop_back();
				dq.push_back(r);
				r++;
			}
			while (l < s.size() && s[l].x + t[i].x < -D)
			{
				if (!dq.empty() && dq.front() == l) dq.pop_front();
				l++;
			}
			if (!dq.empty()) ans = max(ans, t[i].y + s[dq.front()].y);
		}
	}
	printf("%lld\n", ans);
	return 0;
}