#1183205 (C#(csc)) No.3684 chokudai_niku.png

• 問題: No.3684 chokudai_niku.png
• ユーザー: aketijyuuzou
• 提出日時: 2026-09-05 13:21:00
• 言語: C#(csc) (csc 3.9.0)
• 結果: AC
• 実行時間: 290 ms / 2,000 ms
• コード長: 4,729 bytes
• コンパイル時間: 1,757 ms
• コンパイル使用メモリ: 112,000 KB
• 実行使用メモリ: 59,404 KB
• 最終ジャッジ日時: 2026-09-05 13:21:18
• 合計ジャッジ時間: 17,983 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

ファイルパターン	結果
sample	AC * 3
other	AC * 44

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("5 3");
            WillReturn.Add("600 800 600 600 900");
            WillReturn.Add("500 700 300 200 400");
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 4");
            WillReturn.Add("300 500 3000 0 2000 4000");
            WillReturn.Add("100 600 2000 100000 0 1000");
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("4 2");
            WillReturn.Add("0 0 0 0");
            WillReturn.Add("1 2 3 4");
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = GetSplitArr(InputList[0]);
        long M = wkArr[1];

        long[] AArr = GetSplitArr(InputList[1]);
        long[] BArr = GetSplitArr(InputList[2]);
        long UB=AArr.GetUpperBound(0);

        var DiffList = new List<long>();
        for (long I = 0; I <= AArr.GetUpperBound(0); I++) {
            long Diff = AArr[I] - BArr[I];
            Diff = Math.Max(0, Diff);
            DiffList.Add(Diff);
        }

        long Answer = 0;
        var Ins_Fenwick_Tree = new Fenwick_Tree(DiffList);
        for (long I = 0; I <= UB; I++) {
            long RangeSta = I;
            long RangeEnd = I+M-1;
            if (RangeEnd > UB) continue;
            long RangeSum = Ins_Fenwick_Tree.GetSum(RangeSta, RangeEnd);
            Answer = Math.Max(Answer, RangeSum);
        }
        Console.WriteLine(Answer);
    }
}

// フェニック木
#region Fenwick_Tree
internal class Fenwick_Tree
{
    private long[] mBitArr;
    private long mExternalArrUB;

    // ノードのIndexの列挙を返す
    internal IEnumerable<long> GetNodeIndEnum()
    {
        for (long I = 0; I <= mExternalArrUB; I++) {
            yield return I;
        }
    }

    // 木のノードのUBを返す
    internal long GetUB()
    {
        return mExternalArrUB;
    }

    // コンストラクタ(外部配列のUBのみ指定)
    internal Fenwick_Tree(long pExternalArrUB)
    {
        mExternalArrUB = pExternalArrUB;

        // フェニック木の外部配列は0オリジンで、
        // フェニック木の内部配列は1オリジンなため、2を足す
        mBitArr = new long[pExternalArrUB + 2];
    }

    // コンストラクタ(初期化用の配列指定)
    internal Fenwick_Tree(long[] pArr)
        : this(pArr.GetUpperBound(0))
    {
        for (long I = 0; I <= pArr.GetUpperBound(0); I++) {
            this.Add(I, pArr[I]);
        }
    }

    // コンストラクタ(初期化用のList指定)
    internal Fenwick_Tree(List<long> pList)
        : this(pList.Count - 1)
    {
        for (int I = 0; I <= pList.Count - 1; I++) {
            this.Add(I, pList[I]);
        }
    }

    // Indのチェック
    private void IndCheck(long pInd)
    {
        if (pInd < 0) throw new Exception("pInd < 0");
        if (mExternalArrUB < pInd) throw new Exception("UB < pInd");
    }

    // Indの大小チェック
    private void IndRangeCheck(long pSta, long pEnd)
    {
        IndCheck(pSta);
        IndCheck(pEnd);
        if (pSta > pEnd) throw new Exception("pSta > pEnd");
    }

    // インデクサ
    internal long this[long pInd]
    {
        get { return GetSum(pInd, pInd); }
        set { Add(pInd, value - GetSum(pInd, pInd)); }
    }

    // [pSta,pEnd] のSumを返す
    internal long GetSum(long pSta, long pEnd)
    {
        IndRangeCheck(pSta, pEnd);

        long Result = GetSum(pEnd);
        if (pSta > 0) {
            Result -= GetSum(pSta - 1);
        }
        return Result;
    }

    // [0,pEnd] のSumを返す
    internal long GetSum(long pEnd)
    {
        IndCheck(pEnd);

        pEnd++; // 1オリジンに変更

        long Sum = 0;
        while (pEnd >= 1) {
            Sum += mBitArr[pEnd];
            pEnd -= pEnd & -pEnd;
        }
        return Sum;
    }

    // [I] に Xを加算
    internal void Add(long pI, long pX)
    {
        IndCheck(pI);

        pI++; // 1オリジンに変更

        while (pI <= mBitArr.GetUpperBound(0)) {
            mBitArr[pI] += pX;
            pI += pI & -pI;
        }
    }
}
#endregion