結果
問題 | No.545 ママの大事な二人の子供 |
ユーザー | neko_the_shadow |
提出日時 | 2018-06-15 20:30:44 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 2,390 bytes |
コンパイル時間 | 2,931 ms |
コンパイル使用メモリ | 107,776 KB |
実行使用メモリ | 39,764 KB |
最終ジャッジ日時 | 2024-06-30 14:55:34 |
合計ジャッジ時間 | 5,511 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System;using System.Collections.Generic;using System.Linq;namespace _545{class Program{static void Main(string[] args){var n = int.Parse(Console.ReadLine());var inputs = Enumerable.Range(0, n).Select(_ =>{var line = Console.ReadLine().Split().Select(long.Parse).ToList();return Tuple.Create(line[0], line[1]);}).ToList();// 入力の前半分と後半分で全列挙を行う。var len = inputs.Count;var diffs1 = CreateDiffs(inputs, 0, len / 2);var diffs2 = CreateDiffs(inputs, len / 2, len);long best = long.MaxValue;int len2 = diffs2.Count;foreach (long diff1 in diffs1){// diffs2のうち、-diff1に最も近いものを探す(2分探索)int low = 0, high = len2 - 1;while (low < high){int mid = (low + high) / 2;if (diffs2[mid] < -diff1){low = mid + 1;}else{high = mid;}}// low-1, low, low+1から答えを探す。for (int idx = low - 1; idx < low + 2; idx++){if (0 <= idx && idx < len2){long diff2 = diffs2[idx];best = Math.Min(best, Math.Abs(diff1 + diff2));}}}Console.WriteLine(best);}static List<long> CreateDiffs(List<Tuple<long, long>> inputs, int start, int end){var diffs = new HashSet<long>() { 0 };for (int i = start; i < end; i++){var input = inputs[i];var nexts = new HashSet<long>();foreach (var diff in diffs){nexts.Add(diff + input.Item1);nexts.Add(diff - input.Item2);}diffs = nexts;}var answer = diffs.ToList();answer.Sort();return answer;}}}