結果
問題 | No.838 Noelちゃんと星々3 |
ユーザー | claw88 |
提出日時 | 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.
ソースコード
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);}