結果

問題 No.838 Noelちゃんと星々3
ユーザー claw88claw88
提出日時 2019-06-14 22:24:45
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 122 ms / 2,000 ms
コード長 9,396 bytes
コンパイル時間 1,909 ms
コンパイル使用メモリ 118,208 KB
実行使用メモリ 45,908 KB
最終ジャッジ日時 2024-11-14 06:43:57
合計ジャッジ時間 4,253 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 120 ms
42,204 KB
testcase_01 AC 122 ms
45,908 KB
testcase_02 AC 120 ms
45,896 KB
testcase_03 AC 121 ms
43,856 KB
testcase_04 AC 122 ms
42,084 KB
testcase_05 AC 29 ms
24,088 KB
testcase_06 AC 28 ms
23,940 KB
testcase_07 AC 28 ms
23,960 KB
testcase_08 AC 29 ms
24,216 KB
testcase_09 AC 28 ms
22,196 KB
testcase_10 AC 28 ms
21,816 KB
testcase_11 AC 29 ms
26,000 KB
testcase_12 AC 28 ms
23,984 KB
testcase_13 AC 29 ms
26,368 KB
testcase_14 AC 28 ms
26,244 KB
testcase_15 AC 29 ms
26,364 KB
testcase_16 AC 28 ms
23,856 KB
testcase_17 AC 27 ms
24,328 KB
testcase_18 AC 29 ms
24,192 KB
testcase_19 AC 29 ms
24,088 KB
testcase_20 AC 28 ms
26,256 KB
testcase_21 AC 27 ms
24,216 KB
testcase_22 AC 28 ms
24,088 KB
testcase_23 AC 29 ms
26,240 KB
testcase_24 AC 29 ms
24,112 KB
testcase_25 AC 28 ms
23,980 KB
testcase_26 AC 28 ms
24,212 KB
testcase_27 AC 28 ms
24,112 KB
testcase_28 AC 27 ms
24,052 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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;
using System.IO;
using SB = System.Text.StringBuilder;
//using System.Threading.Tasks;
//using System.Text.RegularExpressions;
//using System.Globalization;
//using System.Diagnostics;
using static System.Console;
using System.Numerics;
using static System.Math;
using pair = Pair<int, int>;
class Program
{
static void Main()
{
//SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
new Program().solve();
Out.Flush();
}
readonly Scanner cin = new Scanner();
readonly int[] dd = { 0, 1, 0, -1, 0 }; //→↓←↑
readonly int mod = 1000000007;
readonly int dom = 998244353;
bool chmax<T>(ref T a, T b) where T : IComparable<T> { if (a.CompareTo(b) < 0) { a = b; return true; } return false; }
bool chmin<T>(ref T a, T b) where T : IComparable<T> { if (b.CompareTo(a) < 0) { a = b; return true; } return false; }
long[] Y;
long calc(int i, int j)
{
return Abs(Y[i] - Y[j]);
}
void solve()
{
int N = cin.nextint;
Y = cin.scanlong;
Array.Sort(Y);
//Y[0]Y[1]
var dp = new long[N][];
for (int i = 0; i < N; i++)
{
dp[i] = new long[2];
for (int j = 0; j < 2; j++)
{
dp[i][j] = long.MaxValue / 3;
}
}
//dp[i][0]
//dp[i][1]
dp[0][1] = 0;
for (int i = 1; i < N; i++)
{
chmin(ref dp[i][0], dp[i - 1][1] + Y[i] - Y[i - 1]);
chmin(ref dp[i][1], dp[i - 1][0]);
chmin(ref dp[i][0], dp[i - 1][0] + Y[i] - Y[i - 1]);
if (Y[i - 1] == Y[i] && i >= 2)
{
chmin(ref dp[i][0], dp[i - 2][0]);
}
//WriteLine(dp[i][0] + " " + dp[i][1]);
}
WriteLine(dp[N - 1][0]);
//var S = new SegTree<long>(N, (x, y) => x + y, 0, Y);
//var P = new LongMedianQueue();
//var L = new long[N];
//for (int i = 0; i < N; i++)
//{
// P.Enqueue(Y[i]);
// L[i] = P.Med;
//}
//var R = new long[N];
//P = new LongMedianQueue();
//for (int i = N - 1; i >= 0; i--)
//{
// P.Enqueue(Y[i]);
// R[i] = P.Med;
//}
//if (Y[0] == Y[N - 1])
//{
// WriteLine(1);
// return;
//}
//var ans = long.MaxValue;
//for (int i = 0; i < N - 1; i++)
//{
// var m = L[i];
// var id = Y.lower_bound(m);
// var sum = m * id - S[0, id - 1];
// sum += S[id + 1, i] - (i - id) * m;
// m = R[i + 1];
// id = Y.lower_bound(m);
// sum += m * (id - i) - S[i + 1, id];
// sum += S[id, N - 1] - (N - id) * m;
// chmin(ref ans, sum);
//}
//WriteLine(ans);
}
}
/// <OriginalAuthor>riantkb</OriginalAuthor>
class SegTree<T>
{
readonly int n;
int s, t;
T[] tr;
readonly Func<T, T, T> f;
readonly T exnum;
/// <summary>
/// 1
/// </summary>
/// <param name="m"></param>
/// <param name="f"></param>
/// <param name="ex"></param>
public SegTree(int m, Func<T, T, T> f, T ex)
{
this.f = f; exnum = ex; n = 1;
while (n < m) n <<= 1;
tr = new T[(n << 1) - 1];
for (int i = 0; i < tr.Length; i++) tr[i] = ex;
}
public SegTree(int m, Func<T, T, T> f, T ex, T ini) : this(m, f, ex)
{
for (int i = 0; i < m; i++) Assign(i, ini);
All_Update();
}
public SegTree(int m, Func<T, T, T> f, T ex, IList<T> ini) : this(m, f, ex)
{
for (int i = 0; i < m; i++) Assign(i, ini[i]);
All_Update();
}
public T Look(int j) => tr[j + n - 1];
public T Peek() => tr[0];
/// <summary>
///
/// </summary>
/// <param name="j"></param>
/// <param name="x"></param>
public void Assign(int j, T x) => tr[j + n - 1] = x;
public void Update(int j, T x)
{
Assign(j, x);
Update(j);
}
public void Update(int j)
{
int i = j + n - 1;
while (i > 0) { i = i - 1 >> 1; tr[i] = f(tr[i << 1 | 1], tr[i + 1 << 1]); }
}
public void All_Update() { for (int i = n - 2; i >= 0; i--) tr[i] = f(tr[i << 1 | 1], tr[i + 1 << 1]); }
/// <summary>
/// return node[s, t]
/// </summary>
/// <param name="s"> 0-indexed</param>
/// <param name="t"> 0-indexed</param>
/// <returns>node[s, t]</returns>
public T this[int s, int t] => Run(s, t);
T Run(int s, int t) { t++; this.s = s; this.t = t; return Query(0, 0, n); }
T Query(int k, int l, int r) => r <= s || t <= l ? exnum : s <= l && r <= t ? tr[k]
: f(Query(k << 1 | 1, l, l + r >> 1), Query(k + 1 << 1, l + r >> 1, r));
}
class LongMedianQueue
{
public bool even;
public LongPriorityQueue left, right;
public LongMedianQueue()
{
left = new LongPriorityQueue();
right = new LongPriorityQueue(-1);
even = true;
}
public void Enqueue(long x)
{
even = !even;
if (!Any || x.CompareTo(Med) < 0)
{
left.Enqueue(x);
if (even) right.Enqueue(left.Dequeue());
}
else
{
right.Enqueue(x);
if (!even) left.Enqueue(right.Dequeue());
}
}
public long Dequeue(long x)
{
even = !even;
var ret = left.Dequeue();
if (!even) left.Enqueue(right.Dequeue());
return ret;
}
public int Count => left.Count + right.Count;
public bool Any => left.Count > 0;
public long Med => left.Peek();
}
class LongPriorityQueue
{
List<long> heap;
readonly int cmp;
public LongPriorityQueue(int cmp = 1) { heap = new List<long>(); this.cmp = cmp; }
public void Enqueue(long x)
{
Sum += x;
heap.Add(x);
int i = Count++;
while (i > 0)
{
int p = (i - 1) >> 1;
if (x.CompareTo(heap[p]) * cmp <= 0) break;
heap[i] = heap[p]; i = p;
}
heap[i] = x;
}
public long Dequeue()
{
var ret = heap[0]; var x = heap[--Count];
Sum -= ret;
int i = 0;
while ((i << 1) + 1 < Count)
{
int a = (i << 1) + 1; int b = (i << 1) + 2;
if (b < Count && heap[a].CompareTo(heap[b]) * cmp < 0) a = b;
if (x.CompareTo(heap[a]) * cmp >= 0) break;
heap[i] = heap[a]; i = a;
}
heap[i] = x; heap.RemoveAt(Count);
return ret;
}
public long Sum { get; private set; }
public int Count { get; private set; }
public bool Any => Count > 0;
public long Peek() => heap[0];
}
static class Ex
{
public static void join<T>(this IEnumerable<T> values, string sep = " ") => WriteLine(string.Join(sep, values));
public static string concat<T>(this IEnumerable<T> values) => string.Concat(values);
public static string reverse(this string s) { var t = s.ToCharArray(); Array.Reverse(t); return t.concat(); }
public static int lower_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
{
int low = 0, high = arr.Count;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (arr[mid].CompareTo(val) < 0) low = mid + 1;
else high = mid;
}
return low;
}
public static int upper_bound<T>(this IList<T> arr, T val) where T : IComparable<T>
{
int low = 0, high = arr.Count;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (arr[mid].CompareTo(val) <= 0) low = mid + 1;
else high = mid;
}
return low;
}
}
class Pair<T, U> : IComparable<Pair<T, U>> where T : IComparable<T> where U : IComparable<U>
{
public T f; public U s;
public Pair(T f, U s) { this.f = f; this.s = s; }
public int CompareTo(Pair<T, U> a) => f.CompareTo(a.f) != 0 ? f.CompareTo(a.f) : s.CompareTo(a.s);
public override string ToString() => $"{f} {s}";
}
class Scanner
{
string[] s; int i;
readonly char[] cs = new char[] { ' ' };
public Scanner() { s = new string[0]; i = 0; }
public string[] scan => ReadLine().Split();
public int[] scanint => Array.ConvertAll(scan, int.Parse);
public long[] scanlong => Array.ConvertAll(scan, long.Parse);
public double[] scandouble => Array.ConvertAll(scan, double.Parse);
public string next
{
get
{
if (i < s.Length) return s[i++];
string st = ReadLine();
while (st == "") st = ReadLine();
s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
i = 0;
return next;
}
}
public int nextint => int.Parse(next);
public long nextlong => long.Parse(next);
public double nextdouble => double.Parse(next);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0