結果

問題 No.2139 K Consecutive Sushi
ユーザー kakel-sankakel-san
提出日時 2023-09-22 23:58:11
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 354 ms / 2,000 ms
コード長 6,704 bytes
コンパイル時間 2,609 ms
コンパイル使用メモリ 113,524 KB
実行使用メモリ 58,360 KB
最終ジャッジ日時 2024-07-16 00:32:03
合計ジャッジ時間 9,278 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
25,240 KB
testcase_01 AC 31 ms
26,892 KB
testcase_02 AC 31 ms
25,240 KB
testcase_03 AC 338 ms
53,656 KB
testcase_04 AC 335 ms
54,172 KB
testcase_05 AC 352 ms
55,708 KB
testcase_06 AC 313 ms
55,840 KB
testcase_07 AC 354 ms
53,944 KB
testcase_08 AC 222 ms
51,600 KB
testcase_09 AC 231 ms
49,692 KB
testcase_10 AC 241 ms
49,812 KB
testcase_11 AC 238 ms
47,900 KB
testcase_12 AC 218 ms
49,808 KB
testcase_13 AC 32 ms
27,416 KB
testcase_14 AC 32 ms
26,908 KB
testcase_15 AC 31 ms
23,092 KB
testcase_16 AC 31 ms
25,132 KB
testcase_17 AC 32 ms
24,988 KB
testcase_18 AC 38 ms
27,492 KB
testcase_19 AC 37 ms
25,832 KB
testcase_20 AC 36 ms
25,972 KB
testcase_21 AC 35 ms
27,780 KB
testcase_22 AC 37 ms
26,032 KB
testcase_23 AC 53 ms
24,444 KB
testcase_24 AC 119 ms
35,836 KB
testcase_25 AC 212 ms
45,852 KB
testcase_26 AC 54 ms
26,908 KB
testcase_27 AC 103 ms
38,408 KB
testcase_28 AC 105 ms
38,980 KB
testcase_29 AC 63 ms
29,020 KB
testcase_30 AC 126 ms
38,564 KB
testcase_31 AC 321 ms
53,780 KB
testcase_32 AC 65 ms
30,968 KB
testcase_33 AC 224 ms
58,360 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 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();
    }
    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 AvlTree<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.Delete(dlist[i + 1 - k]);
        }
        var ans = 0L;
        foreach (var ai in a) ans += ai;
        return ans - set.ElementAt(0);
    }
    public class AvlTree<T> where T: IComparable<T>
    {
        private class Node<U> where U: IComparable<U>
        {
            public U Value;
            public Node<U> Lc = null;
            public Node<U> Rc = null;
            public int Height;
            public int Count;
            public int CCount;
            public Node(int height, U value)
            {
                Height = height;
                Count = 1;
                CCount = 1;
                Value = value;
            }
        }
        private Node<T> root = null;
        private bool active;
        static int GetHeight(Node<T> t)
        {
            return t == null ? 0 : t.Height;
        }
        static int GetCount(Node<T> t)
        {
            return t == null ? 0 : t.Count;
        }
        static int GetBalance(Node<T> t)
        {
            return GetHeight(t.Lc) - GetHeight(t.Rc);
        }
        static void Recalc(Node<T> t)
        {
            t.Height = 1 + Math.Max(GetHeight(t.Lc), GetHeight(t.Rc));
            t.Count = t.CCount + GetCount(t.Lc) + GetCount(t.Rc);
        }
        static Node<T> RotateLeft(Node<T> t)
        {
            Node<T> u = t.Rc;
            Node<T> t2 = u.Lc;
            u.Lc = t;
            t.Rc = t2;
            Recalc(u.Lc);
            Recalc(u);
            return u;
        }
        static Node<T> RotateRight(Node<T> t)
        {
            Node<T> u = t.Lc;
            Node<T> t2 = u.Rc;
            u.Rc = t;
            t.Lc = t2;
            Recalc(u.Rc);
            Recalc(u);
            return u;
        }
        static Node<T> RotateLR(Node<T> t)
        {
            t.Lc = RotateLeft(t.Lc);
            return RotateRight(t);
        }
        static Node<T> RotateRL(Node<T> t)
        {
            t.Rc = RotateRight(t.Rc);
            return RotateLeft(t);
        }
        Node<T> BalanceLeft(Node<T> t)
        {
            if (!active) return t;
            var h = GetHeight(t);
            if (GetBalance(t) > 1)
            {
                if (GetBalance(t.Lc) < 0) t = RotateLR(t);
                else t = RotateRight(t);
            }
            Recalc(t);
            active = h != GetHeight(t);
            return t;
        }
        Node<T> BalanceRight(Node<T> t)
        {
            if (!active) return t;
            var h = GetHeight(t);
            if (GetBalance(t) < -1)
            {
                if (GetBalance(t.Rc) > 0) t = RotateRL(t);
                else t = RotateLeft(t);
            }
            Recalc(t);
            active = h != GetHeight(t);
            return t;
        }
        public void Insert(T value)
        {
            active = false;
            root = Insert(root, value);
        }
        Node<T> Insert(Node<T> cur, T value)
        {
            if (cur == null)
            {
                active = true;
                return new Node<T>(1, value);
            }
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Insert(cur.Lc, value);
                return BalanceLeft(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Insert(cur.Rc, value);
                return BalanceRight(cur);
            }
            else
            {
                ++cur.CCount;
                Recalc(cur);
                return cur;
            }
        }
        public void Delete(T value)
        {
            active = false;
            root = Delete(root, value);
        }
        Node<T> Delete(Node<T> cur, T value)
        {
            if (cur == null) return null;
            var d = value.CompareTo(cur.Value);
            if (d < 0)
            {
                cur.Lc = Delete(cur.Lc, value);
                return BalanceRight(cur);
            }
            else if (d > 0)
            {
                cur.Rc = Delete(cur.Rc, value);
                return BalanceLeft(cur);
            }
            else
            {
                --cur.CCount;
                if (cur.CCount == 0)
                {
                    if (cur.Lc != null)
                    {
                        var (k, del) = DeleteMax(cur.Lc);
                        cur.Lc = k;
                        cur.Value = del.Value;
                        cur.CCount = del.CCount;
                        return BalanceRight(cur);
                    }
                    else
                    {
                        active = true;
                        return cur.Rc;
                    }
                }
                else
                {
                    Recalc(cur);
                    return cur;
                }
            }
        }
        (Node<T> keep, Node<T> del) DeleteMax(Node<T> t)
        {
            if (t.Rc == null)
            {
                active = true;
                return (t.Lc, t);
            }
            else
            {
                var (k, d) = DeleteMax(t.Rc);
                t.Rc = k;
                return (BalanceLeft(t), d);
            }
        }
        public T ElementAt(int pos)
        {
            var t = ElementAt(root, pos);
            if (t == null) return default;
            return t.Value;
        }
        Node<T> ElementAt(Node<T> cur, int pos)
        {
            if (pos < GetCount(cur.Lc)) return ElementAt(cur.Lc, pos);
            if (pos < GetCount(cur.Lc) + cur.CCount) return cur;
            if (pos < cur.Count) return ElementAt(cur.Rc, pos);
            return null;
        }
    }
}
0