結果
| 問題 |
No.2139 K Consecutive Sushi
|
| コンテスト | |
| ユーザー |
 kakel-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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 31 |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
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;
}
}
}