結果

問題 No.545 ママの大事な二人の子供
コンテスト
ユーザー azyobuzin
提出日時 2017-07-16 22:31:55
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 1,772 bytes
コンパイル時間 811 ms
コンパイル使用メモリ 82,556 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-11-14 20:07:23
合計ジャッジ時間 1,972 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cassert>
#include <cmath>
#include <iostream>
#include <vector>

std::vector<int64_t> find_all(std::vector<int64_t>& src) {
	assert(src.size() < 31);

	std::vector<int64_t> result;
	result.reserve(1u << src.size());
	result.push_back(0);

	for (int64_t v : src) {
		size_t size = result.size();
		for (int i = 0; i < size; i++) {
			result.push_back(result[i] + v);
		}
	}

	return result;
}

int64_t find_nearest(std::vector<int64_t>& src, int64_t v) {
	int start = 0, end = src.size();
	while (true) {
		assert(start + 1 < end);

		if (start + 2 == end) {
			int64_t xdiff = std::abs(src[start] - v);
			int64_t ydiff = std::abs(src[start + 1] - v);
			if (xdiff <= ydiff) return src[start];
			return src[start + 1];
		}

		int center_index = start + (end - start) / 2;
		if (src[center_index] < v) {
			start = center_index;
		}
		else if (src[center_index] > v) {
			end = center_index + 1;
		}
		else {
			return v;
		}
	}
}

int main()
{
	int n;
	std::cin >> n;

	int64_t a_sum = 0;
	std::vector<int64_t> a_plus_b1;
	a_plus_b1.reserve(n / 2);
	std::vector<int64_t> a_plus_b2;
	a_plus_b2.reserve(n - n / 2);
	for (int i = 0; i < n; i++) {
		int64_t a, b;
		std::cin >> a >> b;
		a_sum += a;
		if (i < n / 2)
			a_plus_b1.push_back(a + b);
		else
			a_plus_b2.push_back(a + b);
	}

	std::vector<int64_t> div1 = find_all(a_plus_b1);
	std::vector<int64_t> div2 = find_all(a_plus_b2);
	std::sort(div2.begin(), div2.end());

	int64_t min_value = INT64_MAX;
	for (int64_t i : div1) {
		int64_t nearest_in_div2 = find_nearest(div2, a_sum - i);
		min_value = std::min(min_value, std::abs(a_sum - i - nearest_in_div2));
	}

	std::cout << min_value << std::endl;
}
0