結果
| 問題 |
No.3050 Prefix Removal
|
| ユーザー |
 tobisatis
|
| 提出日時 | 2025-03-07 21:24:14 |
| 言語 | C# (.NET 8.0.404) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 9,236 bytes |
| コンパイル時間 | 9,366 ms |
| コンパイル使用メモリ | 174,940 KB |
| 実行使用メモリ | 306,088 KB |
| 最終ジャッジ日時 | 2025-03-07 21:25:47 |
| 合計ジャッジ時間 | 89,463 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 38 WA * 2 TLE * 15 |
コンパイルメッセージ
復元対象のプロジェクトを決定しています... /home/judge/data/code/main.csproj を復元しました (114 ミリ秒)。 main -> /home/judge/data/code/bin/Release/net8.0/main.dll main -> /home/judge/data/code/bin/Release/net8.0/publish/
ソースコード
#nullable enable
using System.Numerics;
void Run()
{
var n = Int();
var k = Int();
var az = n.Repeat(Int);
var sz = new long[n + 1];
var mz = new long[n + 1];
mz[n] = 0;
for (var i = n - 1; i >= 0; i--)
{
var a = az[i];
sz[i] = sz[i + 1] + a;
mz[i] = Math.Min(sz[i], mz[i + 1]);
}
var ps = new PrioritySum<long>{ Capacity = k - 1 };
for (var i = 1; i < k; i++) ps.Insert(sz[i]);
var ans = sz[0] + ps.Sum - mz[k + 1] * k;
for (var i = k; i < n; i++)
{
ps.Insert(sz[i]);
var s = ps.Sum;
ans = Math.Max(ans, sz[0] + s - mz[i + 1] * k);
}
Out(ans);
}
#region
AtCoderIO _io_;
var _backend_ = new StandardIOBackend();
_io_ = new(){ Backend = _backend_ };
Run();
_backend_.Flush();
string String() => _io_.Next();
int Int() => int.Parse(String());
void Out(object? x, string? sep = null) => _io_.Out(x, sep);
class AtCoderIO
{
public required StandardIOBackend Backend { get; init; }
Memory<string> _input = Array.Empty<string>();
int _iter = 0;
public string Next()
{
while (_iter >= _input.Length) (_input, _iter) = (Backend.ReadLine().Split(' '), 0);
return _input.Span[_iter++];
}
public void Out(object? x, string? separator = null)
{
if (x == null) return;
separator ??= Environment.NewLine;
if (x is System.Collections.IEnumerable a and not string)
{
var objects = a.Cast<object>();
if (separator == Environment.NewLine && !objects.Any()) return;
x = string.Join(separator, objects);
}
Backend.WriteLine(x);
}
}
class StandardIOBackend
{
readonly StreamReader _sr = new(Console.OpenStandardInput());
readonly StreamWriter _sw = new(Console.OpenStandardOutput()) { AutoFlush = false };
public string ReadLine() => _sr.ReadLine()!;
public void WriteLine(object? value) => _sw.WriteLine(value);
public void Flush() => _sw.Flush();
}
#endregion
static class Extensions
{
public static T[] Repeat<T>(this int time, Func<T> F) => Enumerable.Range(0, time).Select(_ => F()).ToArray();
}
abstract class SelfBalancingTreeBase<T>
{
protected class Node
{
public required T Data { get; set; }
public Node? L { get; set; }
public Node? R { get; set; }
public int Height { get; set; } = 1;
public int Size { get; set; } = 1;
public Node? this[bool right]
{
get => right ? R : L;
set { if (right) R = value; else L = value; }
}
}
protected static Node At(Node? node, int index)
{
while (node != null)
{
var ls = Size(node.L);
if (index == ls) return node;
var right = index > ls;
if (right) index -= ls + 1;
node = node[right];
}
throw new IndexOutOfRangeException();
}
protected Node? Root { get; set; }
protected static int Size(Node? node) => node?.Size ?? 0;
protected static int Height(Node? node) => node?.Height ?? 0;
protected static int HeightDiff(Node node) => Height(node.R) - Height(node.L);
protected static void Update(Node node)
{
node.Height = Math.Max(Height(node.L), Height(node.R)) + 1;
node.Size = Size(node.L) + Size(node.R) + 1;
}
protected static Node? DeleteMin(Node node, Node swap)
{
if (node.L == null) { swap.Data = node.Data; return node.R; }
node.L = DeleteMin(node.L, swap);
return Balance(node);
}
protected static Node Balance(Node node)
{
var diff = HeightDiff(node);
if (diff < -1 || 1 < diff)
{
var right = diff > 0;
var next = node[right]!;
if (HeightDiff(next) * diff < 0) node[right] = Rotate(next, right);
return Rotate(node, !right);
}
Update(node);
return node;
}
protected static Node Rotate(Node node, bool right)
{
var n0 = node[!right]!;
node[!right] = n0[right];
Update(node);
n0[right] = node;
Update(n0);
return n0;
}
public bool DeleteAt(int index) => Size(Root) != Size(Root = DeleteAt(Root, index));
static Node? DeleteAt(Node? node, int index)
{
if (node == null) return null;
var ls = Size(node.L);
if (index == ls)
{
if (node.R == null) return node.L;
node.R = DeleteMin(node.R, node);
}
else
{
var right = index > ls;
node[right] = DeleteAt(node[right], right ? index - 1 - ls : index);
}
return Balance(node);
}
protected IEnumerator<T> GetEnumerator()
{
var stack = new Stack<Node>();
var lastR = Root;
while (lastR != null || stack.Count > 0)
{
while (lastR != null)
{
stack.Push(lastR);
lastR = lastR.L;
}
var last = stack.Pop();
yield return last.Data;
lastR = last.R;
}
}
public int Count { get => Size(Root); }
}
abstract class SelfBalancingTree<TKey, TValue> : SelfBalancingTreeBase<KeyValuePair<TKey, TValue>> where TKey : IComparable<TKey>
{
public int MaxIndex(TKey key, bool include) => Bound(Root, key, true, include).Item1;
public int MinIndex(TKey key, bool include) => Bound(Root, key, false, include).Item1;
protected static (int, Node?) Bound(Node? node, TKey key, bool max, bool include)
{
var index = max ? -1 : 0;
Node? res = null;
while (node != null)
{
var comp = key.CompareTo(node.Data.Key);
var left = comp < 0 || comp == 0 && (max ^ include);
if (!left) index += Size(node.L) + 1;
if (max ^ left) res = node;
node = left ? node.L : node.R;
}
return (index, res);
}
public int CountKey(TKey key) => MaxIndex(key, true) - MaxIndex(key, false);
public ValueTuple<TKey>? MaxKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, true, include).Item2);
public ValueTuple<TKey>? MinKey(TKey key, bool include) => ToOptionalKey(Bound(Root, key, false, include).Item2);
static ValueTuple<TKey>? ToOptionalKey(Node? node) => node == null ? null : new(node.Data.Key);
protected static Node? Find(Node? node, TKey key)
{
var res = Bound(node, key, false, true).Item2;
return res != null && key.CompareTo(res.Data.Key) == 0 ? res : null;
}
protected static KeyValuePair<TKey, TValue> CreateData(TKey key, TValue value) => new(key, value);
protected void Insert(KeyValuePair<TKey, TValue> data) => Root = Insert(Root, data);
static Node Insert(Node? node, KeyValuePair<TKey, TValue> data)
{
if (node == null) return new Node{ Data = data };
var right = data.Key.CompareTo(node.Data.Key) >= 0;
node[right] = Insert(node[right], data);
return Balance(node);
}
public bool Delete(TKey key) => Size(Root) != Size(Root = Delete(Root, key));
static Node? Delete(Node? node, TKey key)
{
if (node == null) return null;
var comp = key.CompareTo(node.Data.Key);
if (comp == 0)
{
if (node.R == null) return node.L;
node.R = DeleteMin(node.R, node);
}
else
{
var right = comp > 0;
node[right] = Delete(node[right], key);
}
return Balance(node);
}
}
class OrderedMultiSet<T> : SelfBalancingTree<T, ValueTuple> where T : IComparable<T>
{
public bool Contains(T key) => Find(Root, key) != null;
public T At(int index) => At(Root, index).Data.Key;
public void Insert(T key) => Insert(CreateData(key, ValueTuple.Create()));
public new IEnumerator<T> GetEnumerator()
{
using var e = base.GetEnumerator();
while (e.MoveNext()) yield return e.Current.Key;
}
}
class PrioritySum<T> where T : IAdditionOperators<T, T, T>, ISubtractionOperators<T, T, T>, IAdditiveIdentity<T, T>, IComparable<T>
{
public T Sum { get; private set; } = T.AdditiveIdentity;
public int Capacity
{
get => capacity;
set
{
capacity = value;
Calculate();
}
}
int capacity = 0;
readonly OrderedMultiSet<T> upper = new(), lower = new();
public void Insert(T value)
{
upper.Insert(value);
Sum += value;
Calculate();
}
public bool Delete(T value)
{
if (lower.Delete(value)) return true;
if (!upper.Delete(value)) return false;
Sum -= value;
Calculate();
return true;
}
void Calculate()
{
while (upper.Count > Capacity)
{
var min = upper.At(0);
upper.Delete(min);
lower.Insert(min);
Sum -= min;
}
while (upper.Count < Capacity && lower.Count > 0)
{
var max = lower.At(lower.Count - 1);
lower.Delete(max);
upper.Insert(max);
Sum += max;
}
}
}