結果

問題 No.9 モンスターのレベル上げ
ユーザー くれちーくれちー
提出日時 2018-02-01 20:37:42
言語 C#(csc)
(csc 3.9.0)
結果
WA  
実行時間 -
コード長 4,714 bytes
コンパイル時間 1,249 ms
コンパイル使用メモリ 114,176 KB
実行使用メモリ 19,712 KB
最終ジャッジ日時 2024-06-09 21:24:34
合計ジャッジ時間 19,855 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 27 ms
18,816 KB
testcase_01 AC 25 ms
18,816 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 AC 26 ms
18,816 KB
testcase_11 AC 2,140 ms
19,456 KB
testcase_12 AC 2,672 ms
19,584 KB
testcase_13 AC 1,648 ms
19,456 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using static System.Math;
using static Extensions;

public static class Program
{
    public static void Solve()
    {
        var n = I;
        var a = Repeat(n, () => I).ToArray();
        var b = Repeat(n, () => I).ToArray();
        var pq = new BinaryHeap<(int, int)>();
        var max = 0;

        Repeat(n, i =>
        {
            a.ForEach(x => pq.Enqueue((x, 0)));
            Repeat(n, j =>
            {
                j = (i + j >= n) ? (i + j - n) : (i + j);
                var (x, y) = pq.Dequeue();
                max = Max(max, y + 1);
                pq.Enqueue((x + b[j] / 2, y + 1));
            });
            pq.Clear();
        });

        Answer(max);
    }

    static TextScanner _ts;
    static int I => int.Parse(_ts.Next());

    public static void Main()
    {
        var sw = new StreamWriter(Console.OpenStandardOutput());
        sw.NewLine = "\n";
#if DEBUG
        sw.AutoFlush = true;
#else
        sw.AutoFlush = false;
#endif
        Console.SetOut(sw);
        _ts = new TextScanner(Console.In);
        Solve();
        Console.Out.Flush();
    }
}

#region Library
#pragma warning disable
public interface IPriorityQueue<T>
{
    int Count { get; }
    bool Any();
    void Clear();
    void Enqueue(T item);
    T Dequeue();
    T Peek();
}

public class BinaryHeap<T> : IPriorityQueue<T>
{
    private readonly IComparer<T> _comparer;
    private readonly List<T> _t;

    public BinaryHeap() : this(Comparer<T>.Default) { }

    public BinaryHeap(IComparer<T> comparer)
    {
        _t = new List<T>();
        _comparer = comparer;
    }

    public BinaryHeap(int capacity) : this(capacity, Comparer<T>.Default) { }

    public BinaryHeap(int capacity, IComparer<T> comparer)
    {
        _t = new List<T>(capacity);
        _comparer = comparer;
    }

    public int Count { get; private set; }

    public int Capacity => _t.Capacity;

    public bool Any() => this.Count > 0;

    public void Clear()
    {
        _t.Clear();
        this.Count = 0;
    }

    public void TrimExcess() => _t.TrimExcess();

    public void Enqueue(T item)
    {
        var i = this.Count++;
        while (i > 0)
        {
            var p = (i - 1) >> 1;
            if (_comparer.Compare(_t[p], item) <= 0) break;
            Set(i, _t[p]);
            i = p;
        }
        Set(i, item);
    }

    public T Dequeue()
    {
        if (this.Count == 0) throw new InvalidOperationException();
        var ret = _t[0];
        var x = _t[--this.Count];
        var i = 0;
        while ((i << 1) + 1 < this.Count)
        {
            var a = (i << 1) + 1;
            var b = (i << 1) + 2;
            if (b < this.Count && _comparer.Compare(_t[b], _t[a]) < 0) a = b;
            if (_comparer.Compare(_t[a], x) >= 0) break;
            _t[i] = _t[a];
            i = a;
        }
        _t[i] = x;
        return ret;
    }

    public T Peek()
    {
        if (this.Count == 0) throw new InvalidOperationException();
        return _t[0];
    }

    private void Set(int i, T value)
    {
        if (i < _t.Count) _t[i] = value;
        else if (i == _t.Count) _t.Add(value);
        else throw new InvalidOperationException();
    }
}

public class TextScanner
{
    private readonly TextReader _tr;

    public TextScanner(TextReader tr)
    {
        _tr = tr;
    }

    public string Next()
    {
        var sb = new StringBuilder();
        int i;
        do
        {
            i = _tr.Read();
            if (i == -1) throw new EndOfStreamException();
        }
        while (char.IsWhiteSpace((char)i));
        while (i != -1 && !char.IsWhiteSpace((char)i))
        {
            sb.Append((char)i);
            i = _tr.Read();
        }
        return sb.ToString();
    }
}

public static class Constants
{
}

[DebuggerStepThrough]
public static partial class Extensions
{
    public static void Answer(object value)
    {
        Console.WriteLine(value);
        Exit(0);
    }

    public static void Exit(int exitCode)
    {
        Console.Out.Flush();
        Environment.Exit(exitCode);
    }

    public static void ForEach<T>(this IEnumerable<T> source, Action<T> action)
    {
        foreach (var item in source) action(item);
    }

    public static void Repeat(int count, Action<int> action)
    {
        for (var i = 0; i < count; i++) action(i);
    }

    public static IEnumerable<T> Repeat<T>(int count, Func<T> func)
    {
        for (var i = 0; i < count; i++) yield return func();
    }
}

[DebuggerStepThrough]
public static class MathExtensions
{
}
#pragma warning restore
#endregion
0