結果
| 問題 | No.2139 K Consecutive Sushi |
| コンテスト | |
| ユーザー |
 kakel-san
|
| 提出日時 | 2023-09-19 19:56:05 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 1,271 ms / 2,000 ms |
| コード長 | 9,432 bytes |
| 記録 | |
| コンパイル時間 | 2,184 ms |
| コンパイル使用メモリ | 109,824 KB |
| 実行使用メモリ | 44,288 KB |
| 最終ジャッジ日時 | 2024-11-27 19:56:42 |
| 合計ジャッジ時間 | 17,129 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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();
// 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);
}
}
}