#1192834 (C#) No.738 平らな農地

• 問題: No.738 平らな農地
• ユーザー: 👑 kakel-san
• 提出日時: 2026-10-11 00:44:20
• 言語: C# (.NET 10.0.400 + ACL)
• 結果: AC
• 実行時間: 227 ms / 2,000 ms
• コード長: 4,734 bytes
• コンパイル時間: 4,957 ms
• コンパイル使用メモリ: 172,464 KB
• 実行使用メモリ: 56,832 KB
• 最終ジャッジ日時: 2026-10-11 00:44:53
• 合計ジャッジ時間: 18,956 ms
• ジャッジサーバーID （参考情報）: judge4_0 / judge1_0

ファイルパターン	結果
sample	AC * 5
other	AC * 87

コンパイルメッセージ

  復元対象のプロジェクトを決定しています...
  /home/judge/data/code/main.csproj を復元しました (159 ミリ秒)。
  main -> /home/judge/data/code/bin/Release/net10.0/main.dll
  main -> /home/judge/data/code/bin/Release/net10.0/publish/

ソースコード

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(Farm(n, k, a));
    }
    static long Farm(int n, int k, int[] a)
    {
        if (k == 1) return 0;
        var pos = new int[n];
        var lower = new PriorityQueue<int, int>();
        var upper = new PriorityQueue<int, int>();
        var lowersum = 0L;
        var uppersum = 0L;
        for (var i = 0; i < k; ++i)
        {
            lower.Enqueue(i, -a[i]);
            lowersum += a[i];
            pos[i] = 1;
        }
        var ans = long.MaxValue;
        if (k % 2 == 0)
        {
            for (var i = 0; i < k / 2; ++i)
            {
                var cur = lower.Dequeue();
                upper.Enqueue(cur, a[cur]);
                lowersum -= a[cur];
                uppersum += a[cur];
                pos[cur] = 2;
            }
            ans = uppersum - lowersum;
            for (var i = k; i < n; ++i)
            {
                while (pos[lower.Peek()] == 0) lower.Dequeue();
                while (pos[upper.Peek()] == 0) upper.Dequeue();
                if (pos[i - k] == 1)
                {
                    lower.Enqueue(i, -a[i]);
                    lowersum += a[i] - a[i - k];
                    pos[i] = 1;
                }
                else
                {
                    upper.Enqueue(i, a[i]);
                    uppersum += a[i] - a[i - k];
                    pos[i] = 2;
                }
                pos[i - k] = 0;
                if (a[lower.Peek()] > a[upper.Peek()])
                {
                    var take = lower.Dequeue();
                    lowersum -= a[take];
                    upper.Enqueue(take, a[take]);
                    uppersum += a[take];
                    pos[take] = 2;
                    take = upper.Dequeue();
                    uppersum -= a[take];
                    lower.Enqueue(take, -a[take]);
                    lowersum += a[take];
                    pos[take] = 1;
                }
                ans = Math.Min(ans, uppersum - lowersum);
            }
        }
        else
        {
            for (var i = 0; i < k / 2; ++i)
            {
                var cur = lower.Dequeue();
                upper.Enqueue(cur, a[cur]);
                lowersum -= a[cur];
                uppersum += a[cur];
                pos[cur] = 2;
            }
            var midcur = lower.Dequeue();
            pos[midcur] = 3;
            lowersum -= a[midcur];
            ans = uppersum - lowersum;
            for (var i = k; i < n; ++i)
            {
                while (pos[lower.Peek()] == 0) lower.Dequeue();
                while (pos[upper.Peek()] == 0) upper.Dequeue();
                if (pos[i - k] == 1)
                {
                    lower.Enqueue(i, -a[i]);
                    lowersum += a[i] - a[i - k];
                    pos[i] = 1;
                }
                else if (pos[i - k] == 2)
                {
                    upper.Enqueue(i, a[i]);
                    uppersum += a[i] - a[i - k];
                    pos[i] = 2;
                }
                else
                {
                    midcur = i;
                    pos[i] = 3;
                }
                pos[i - k] = 0;
                if (a[midcur] > a[upper.Peek()])
                {
                    var take = upper.Dequeue();
                    upper.Enqueue(midcur, a[midcur]);
                    uppersum += a[midcur] - a[take];
                    pos[midcur] = 2;
                    pos[take] = 3;
                    midcur = take;
                }
                if (a[lower.Peek()] > a[midcur])
                {
                    var take = lower.Dequeue();
                    lower.Enqueue(midcur, -a[midcur]);
                    lowersum += a[midcur] - a[take];
                    pos[midcur] = 1;
                    pos[take] = 3;
                    midcur = take;
                }
                if (a[midcur] > a[upper.Peek()])
                {
                    var take = upper.Dequeue();
                    upper.Enqueue(midcur, a[midcur]);
                    uppersum += a[midcur] - a[take];
                    pos[midcur] = 2;
                    pos[take] = 3;
                    midcur = take;
                }
                ans = Math.Min(ans, uppersum - lowersum);
            }
        }
        return ans;
    }
}