結果

問題 No.2139 K Consecutive Sushi
ユーザー 👑 kakel-sankakel-san
提出日時 2023-09-19 19:56:05
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,561 ms / 2,000 ms
コード長 9,432 bytes
コンパイル時間 1,621 ms
コンパイル使用メモリ 68,808 KB
実行使用メモリ 51,692 KB
最終ジャッジ日時 2023-09-19 19:56:28
合計ジャッジ時間 21,567 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
25,920 KB
testcase_01 AC 69 ms
23,912 KB
testcase_02 AC 68 ms
25,912 KB
testcase_03 AC 1,436 ms
49,760 KB
testcase_04 AC 1,539 ms
49,924 KB
testcase_05 AC 1,523 ms
49,700 KB
testcase_06 AC 1,282 ms
47,800 KB
testcase_07 AC 1,561 ms
49,864 KB
testcase_08 AC 750 ms
49,756 KB
testcase_09 AC 788 ms
51,692 KB
testcase_10 AC 902 ms
49,720 KB
testcase_11 AC 848 ms
47,692 KB
testcase_12 AC 682 ms
49,788 KB
testcase_13 AC 67 ms
25,920 KB
testcase_14 AC 68 ms
23,840 KB
testcase_15 AC 69 ms
23,856 KB
testcase_16 AC 69 ms
25,928 KB
testcase_17 AC 70 ms
21,996 KB
testcase_18 AC 83 ms
26,240 KB
testcase_19 AC 83 ms
28,180 KB
testcase_20 AC 83 ms
24,180 KB
testcase_21 AC 79 ms
25,980 KB
testcase_22 AC 84 ms
28,188 KB
testcase_23 AC 157 ms
32,620 KB
testcase_24 AC 430 ms
39,684 KB
testcase_25 AC 918 ms
44,416 KB
testcase_26 AC 148 ms
32,848 KB
testcase_27 AC 379 ms
38,320 KB
testcase_28 AC 360 ms
38,428 KB
testcase_29 AC 200 ms
33,816 KB
testcase_30 AC 473 ms
39,072 KB
testcase_31 AC 1,440 ms
43,620 KB
testcase_32 AC 195 ms
34,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

using System;
using static System.Console;
using System.Linq;
using System.Collections.Generic;
class Program
{
    static int NN => int.Parse(ReadLine());
    static int[] NList => ReadLine().Split().Select(int.Parse).ToArray();
    public static void Main()
    {
        Solve();
        // Test();
    }
    static void Test()
    {
        var r = new Random();
        var n = 200000;
        var k = 100000;
        var a = new int[n];
        for (var i = 0; i < n; ++i) a[i] = r.Next(1, 1000000000);
        var start = DateTime.Now;
        WriteLine(Sushi(n, k, a));
        WriteLine((DateTime.Now - start).TotalSeconds);
    }
    static void Solve()
    {
        var c = NList;
        var (n, k) = (c[0], c[1]);
        var a = NList;
        WriteLine(Sushi(n, k, a));
    }
    static long Sushi(int n, int k, int[] a)
    {
        var set = new CMultiSet<long>();
        set.Insert(0);
        var dlist = new long[n + 1];
        for (var i = 0; i < n; ++i)
        {
            var min = set.ElementAt(0);
            dlist[i + 1] = min + a[i];
            set.Insert(dlist[i + 1]);
            if (i + 1 - k >= 0) set.Remove(dlist[i + 1 - k]);
        }
        var ans = 0L;
        foreach (var ai in a) ans += ai;
        return (ans - set.ElementAt(0));
    }
    public class CSet<T> where T : IComparable
    {
        protected SB_BST<T>.Node _root;

        public T this[int idx]{ get { return ElementAt(idx); } }

        public int Count()
        {
            return SB_BST<T>.Count(_root);
        }

        public virtual void Insert(T v)
        {
            if (_root == null) _root = new SB_BST<T>.Node(v);
            else
            {
                if (SB_BST<T>.Find(_root, v) != null) return;
                _root = SB_BST<T>.Insert(_root, v);
            }
        }

        public void Clear()
        {
            _root = null;
        }

        public void Remove(T v)
        {
            _root = SB_BST<T>.Remove(_root, v);
        }

        public bool Contains(T v)
        {
            return SB_BST<T>.Contains(_root, v);
        }

        public T ElementAt(int k)
        {
            var node = SB_BST<T>.FindByIndex(_root, k);
            if (node == null) throw new IndexOutOfRangeException();
            return node.Value;
        }

        public int Count(T v)
        {
            return SB_BST<T>.UpperBound(_root, v) - SB_BST<T>.LowerBound(_root, v);
        }
        /// <summary>指定した値以上の要素のうち最小のインデックスを取得</summary>
        public int LowerBound(T v)
        {
            return SB_BST<T>.LowerBound(_root, v);
        }
        /// <summary>指定した値より大きい要素のうち最小のインデックスを取得</summary>
        public int UpperBound(T v)
        {
            return SB_BST<T>.UpperBound(_root, v);
        }

        public Tuple<int, int> EqualRange(T v)
        {
            if (!Contains(v)) return new Tuple<int, int>(-1, -1);
            return new Tuple<int, int>(SB_BST<T>.LowerBound(_root, v), SB_BST<T>.UpperBound(_root, v) - 1);
        }

        public List<T> ToList()
        {
            return new List<T>(SB_BST<T>.Enumerate(_root));
        }
    }
    public class CMultiSet<T> : CSet<T> where T : IComparable
    {
        public override void Insert(T v)
        {
            if (_root == null) _root = new SB_BST<T>.Node(v);
            else _root = SB_BST<T>.Insert(_root, v);
        }
    }
    public class SB_BST<T> where T : IComparable
    {
        public class Node
        {
            public T Value;
            public Node LChild;
            public Node RChild;
            public int Count;     //size of the sub tree

            public Node(T v)
            {
                Value = v;
                Count = 1;
            }
        }

        static Random _rnd = new Random();

        public static int Count(Node t)
        {
            return t == null ? 0 : t.Count;
        }

        static Node Update(Node t)
        {
            t.Count = Count(t.LChild) + Count(t.RChild) + 1;
            return t;
        }

        public static Node Merge(Node l, Node r)
        {
            if (l == null || r == null) return l == null ? r : l;

            if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
            {
                l.RChild = Merge(l.RChild, r);
                return Update(l);
            }
            else
            {
                r.LChild = Merge(l, r.LChild);
                return Update(r);
            }
        }

        /// <summary>
        /// split as [0, k), [k, n)
        /// </summary>
        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) return new Tuple<Node, Node>(null, null);
            if (k <= Count(t.LChild))
            {
                var s = Split(t.LChild, k);
                t.LChild = s.Item2;
                return new Tuple<Node, Node>(s.Item1, Update(t));
            }
            else
            {
                var s = Split(t.RChild, k - Count(t.LChild) - 1);
                t.RChild = s.Item1;
                return new Tuple<Node, Node>(Update(t), s.Item2);
            }
        }

        public static Node Remove(Node t, T v)
        {
            if (Find(t, v) == null) return t;
            return RemoveAt(t, LowerBound(t, v));
        }

        public static Node RemoveAt(Node t, int k)
        {
            var s = Split(t, k);
            var s2 = Split(s.Item2, 1);
            return Merge(s.Item1, s2.Item2);
        }

        public static bool Contains(Node t, T v)
        {
            return Find(t, v) != null;
        }

        public static Node Find(Node t, T v)
        {
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp > 0) t = t.LChild;
                else if (cmp < 0) t = t.RChild;
                else break;
            }
            return t;
        }

        public static Node FindByIndex(Node t, int idx)
        {
            if (t == null) return null;

            var currentIdx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                if (currentIdx == idx) return t;
                if (currentIdx > idx)
                {
                    t = t.LChild;
                    currentIdx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else
                {
                    t = t.RChild;
                    currentIdx += (Count(t == null ? null : t.LChild) + 1);
                }
            }

            return null;
        }

        public static int UpperBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var ret = Int32.MaxValue;
            var idx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                    
                if (cmp > 0)
                {
                    ret = Math.Min(ret, idx);
                    t = t.LChild;
                    idx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else if (cmp <= 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static int LowerBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var idx = Count(t) - Count(t.RChild) - 1;
            var ret = Int32.MaxValue;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp >= 0)
                {
                    if (cmp == 0) ret = Math.Min(ret, idx);
                    t = t.LChild;
                    if (t == null) ret = Math.Min(ret, idx);
                    idx -= t == null ? 0 : (Count(t.RChild) + 1);
                }
                else if (cmp < 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                    if (t == null) return idx;
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static Node Insert(Node t, T v)
        {
            var ub = LowerBound(t, v);
            return InsertByIdx(t, ub, v);
        }

        static Node InsertByIdx(Node t, int k, T v)
        {
            var s = Split(t, k);
            return Merge(Merge(s.Item1, new Node(v)), s.Item2);
        }

        public static IEnumerable<T> Enumerate(Node t)
        {
            var ret = new List<T>();
            Enumerate(t, ret);
            return ret;
        }

        static void Enumerate(Node t, List<T> ret)
        {
            if (t == null) return;
            Enumerate(t.LChild, ret);
            ret.Add(t.Value);
            Enumerate(t.RChild, ret);
        }
    }
}
0