結果
| 問題 |
No.837 Noelちゃんと星々2
|
| コンテスト | |
| ユーザー |
 sekiya9311
|
| 提出日時 | 2019-06-14 22:32:51 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,735 bytes |
| コンパイル時間 | 2,679 ms |
| コンパイル使用メモリ | 117,776 KB |
| 実行使用メモリ | 50,184 KB |
| 最終ジャッジ日時 | 2024-11-14 06:59:31 |
| 合計ジャッジ時間 | 5,939 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 18 WA * 11 |
コンパイルメッセージ
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;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
namespace ProgrammingContest
{
class Writer : IDisposable
{
private System.IO.TextWriter Out { get; }
private StringBuilder Sb { get; }
private bool IsReactive { get; }
public Writer(string path)
: this(new System.IO.StreamWriter(path))
{
}
public Writer(bool isReactive)
: this(null, isReactive)
{
}
public Writer(System.IO.TextWriter writer = null, bool isReactive = false)
{
this.Out = (writer ?? Console.Out);
this.IsReactive = isReactive;
if (!this.IsReactive)
{
this.Sb = new StringBuilder();
}
}
public void Dispose()
{
if (!this.IsReactive)
{
this.Out.Write(Sb.ToString());
}
if (!this.Out.Equals(Console.Out))
{
this.Out.Dispose();
}
}
public void Write(object val)
{
if (this.IsReactive)
{
this.Out.Write(val.ToString());
this.Out.Flush();
}
else
{
this.Sb.Append(val.ToString());
}
}
public void WriteFormat(string format, params object[] vals)
{
if (this.IsReactive)
{
this.Out.Write(format, vals);
this.Out.Flush();
}
else
{
this.Sb.AppendFormat(format, vals);
}
}
public void WriteLine(object val = null)
=> this.WriteFormat((val?.ToString() ?? string.Empty) + Environment.NewLine);
public void WriteLine(int val)
=> this.WriteLine(val.ToString());
public void WriteLine(long val)
=> this.WriteLine(val.ToString());
public void WriteLine(string val)
=> this.WriteLine((object)val);
public void WriteLine(string format, params object[] vals)
=> this.WriteFormat(format + Environment.NewLine, vals);
}
class Scanner : IDisposable
{
private Queue<string> Buffer { get; }
private char[] Sep { get; }
private System.IO.TextReader Reader { get; }
public Scanner(string path, char[] sep = null)
: this(new System.IO.StreamReader(path), sep)
{
}
public Scanner(System.IO.TextReader reader = null,
char[] sep = null)
{
this.Buffer = new Queue<string>();
this.Sep = (sep ?? new char[] { ' ' });
this.Reader = (reader ?? Console.In);
}
private void CheckBuffer()
{
if (this.Buffer.Count == 0 && this.Reader.Peek() != -1)
{
string str = string.Empty;
for (; string.IsNullOrEmpty(str) || string.IsNullOrWhiteSpace(str);
str = this.Reader.ReadLine()) ;
var strs = str.Split(this.Sep)
.Where(el => !(string.IsNullOrEmpty(el) || string.IsNullOrWhiteSpace(el)));
foreach (var el in strs)
{
this.Buffer.Enqueue(el);
}
}
}
public void Dispose()
{
if (!this.Reader.Equals(Console.In))
{
this.Reader.Dispose();
}
}
public string Next()
{
this.CheckBuffer();
return this.Buffer.Dequeue();
}
public string[] GetStringArray(int N)
=> Enumerable.Range(0, N)
.Select(e => this.Next())
.ToArray();
public int NextInt()
=> int.Parse(this.Next());
public int[] GetIntArray(int N)
=> Enumerable.Range(0, N)
.Select(e => this.NextInt())
.ToArray();
public double NextDouble()
=> double.Parse(this.Next());
public double[] GetdoubleArray(int N)
=> Enumerable.Range(0, N)
.Select(e => this.NextDouble())
.ToArray();
public long NextLong()
=> long.Parse(this.Next());
public long[] GetLongArray(int N)
=> Enumerable.Range(0, N)
.Select(e => this.NextLong())
.ToArray();
public BigInteger NextBigInt()
=> BigInteger.Parse(this.Next());
public BigInteger[] GetBigIntArray(int N)
=> Enumerable.Range(0, N)
.Select(e => this.NextBigInt())
.ToArray();
public bool IsEnd
{
get
{
this.CheckBuffer();
return this.Buffer.Count == 0;
}
}
}
class MainClass : IDisposable
{
private Scanner Sc { get; }
private Writer Wr { get; }
private string InFilePath => "in.txt";
private string OutFilePath => "out.txt";
public MainClass()
{
this.Wr = new Writer(this.IsReactive);
//this.Wr = new Writer(this.OutFilePath);
#if DEBUG
if (!this.IsReactive)
{
this.Sc = new Scanner(this.InFilePath);
}
else
{
this.Sc = new Scanner();
}
#else
this.Sc = new Scanner();
#endif
this.Solve();
}
static void Main(string[] args)
{
using (new MainClass()) { }
}
public void Dispose()
{
this.Sc?.Dispose();
this.Wr?.Dispose();
#if DEBUG
Console.WriteLine("press any key to continue...");
Console.ReadKey();
#endif
}
void Solve()
{
int N = Sc.NextInt();
var Y = Sc.GetLongArray(N);
Array.Sort(Y);
var dCnt = new HashSet<long>(Y).Count;
if (dCnt == 1)
{
Wr.WriteLine(1);
return;
}
else if (dCnt == 2)
{
Wr.WriteLine(0);
return;
}
long[] acc = new long[N + 1];
for (int i = 0; i < N; i++)
{
acc[i + 1] = acc[i] + Y[i];
}
Func<int, int, long> CalcSum = (l, r) => acc[r] - acc[l];
long ans = (long)1e18;
for (int i = 1; i < N - 1; i++)
{
// [l_l, l_r), [r_l, r_r)
int l_l = 0;
int l_r = i;
int r_l = i;
int r_r = N;
long left = (long)1e18;
{
var key = (l_r - l_l) / 2;
if ((l_r - l_l) % 2 == 0)
{
left = Math.Abs(CalcSum(l_l, key) - Y[key] * (key - l_l)) + Math.Abs(CalcSum(key, l_r) - Y[key] * (l_r - key));
key++;
left = Math.Min(left, Math.Abs(CalcSum(l_l, key) - Y[key] * (key - l_l)) + Math.Abs(CalcSum(key, l_r) - Y[key] * (l_r - key)));
}
else
{
left = Math.Abs(CalcSum(l_l, key) - Y[key] * (key - l_l)) + Math.Abs(CalcSum(key, l_r) - Y[key] * (l_r - key));
}
}
long right = (long)1e18;
{
var key = (r_r - r_l) / 2 + r_l - 1;
if ((r_r - r_l) % 2 == 0)
{
right = Math.Abs(CalcSum(r_l, key) - Y[key] * (key - r_l)) + Math.Abs(CalcSum(key, r_r) - Y[key] * (r_r - key));
key++;
right = Math.Min(right, Math.Abs(CalcSum(r_l, key) - Y[key] * (key - r_l)) + Math.Abs(CalcSum(key, r_r) - Y[key] * (r_r - key)));
}
else
{
right = Math.Abs(CalcSum(r_l, key) - Y[key] * (key - r_l)) + Math.Abs(CalcSum(key, r_r) - Y[key] * (r_r - key));
}
}
//Wr.WriteLine($"{Y[(l_r - l_l)/2]}, {Y[(r_r - r_l) / 2 + r_l - 1]}");
ans = Math.Min(ans, left + right);
}
Wr.WriteLine(ans);
}
private bool IsReactive => false; // TODO: reactive check !!
}
}