結果

問題 No.545 ママの大事な二人の子供
ユーザー neko_the_shadowneko_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.

ソースコード

diff #
プレゼンテーションモードにする

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;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0