AGC008-B Contiguous Repainting

問題へのリンク

C#のソース

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("-10 10 -10 10 -10");
            //10
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4 2");
            WillReturn.Add("10 -10 -10 10");
            //20
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 1");
            WillReturn.Add("-10");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 5");
            WillReturn.Add("5 -4 -5 -8 -4 7 2 -4 0 7");
            //17
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        long[] wkArr = InputList[0].Split(' ').Select(pX => long.Parse(pX)).ToArray();
        long K = wkArr[1];

        long[] AArr = InputList[1].Split(' ').Select(pX => long.Parse(pX)).ToArray();

        long Result = Solve(K, AArr);
        Console.WriteLine(Result);
    }

    static long Solve(long pK, long[] pArr)
    {
        long UB = pArr.GetUpperBound(0);

        long[] RunSum = new long[UB + 1];
        long[] RunSumPlusOnly = new long[UB + 1];

        // 累積和と、累積和(正の数のみ)を求める
        for (long I = 0; I <= UB; I++) {
            RunSum[I] = pArr[I];
            RunSumPlusOnly[I] = Math.Max(0, pArr[I]);
            if (I > 0) {
                RunSum[I] += RunSum[I - 1];
                RunSumPlusOnly[I] += RunSumPlusOnly[I - 1];
            }
        }

        long AllSumPlusOnly = pArr.Where(pX => pX > 0).Sum();

        var KouhoList = new List<long>();
        for (long I = 0; I <= UB; I++) {
            long RangeSta = I;
            long RangeEnd = I + pK - 1;
            if (UB < RangeEnd) break;

            long RangePlusSum = DeriveRangeSum(RunSumPlusOnly, RangeSta, RangeEnd);
            long RestPlusSum = AllSumPlusOnly - RangePlusSum;

            // この区間を全部白にした場合
            KouhoList.Add(RestPlusSum);

            // この区間を全部黒にした場合
            long RangeSum = DeriveRangeSum(RunSum, RangeSta, RangeEnd);
            KouhoList.Add(RestPlusSum + RangeSum);
        }
        return KouhoList.Max();
    }

    // 配列と区間開始と区間終了を引数として、区間の和を返す
    static long DeriveRangeSum(long[] pArr, long pSta, long pEnd)
    {
        long RangeSum = pArr[pEnd];
        if (pSta > 0) {
            RangeSum -= pArr[pSta - 1];
        }
        return RangeSum;
    }
}

解説

オセロセットを使って考察すると
最後の反転する駒以外は、自由に白と黒を設定できると分かります。

なので、累積和と累積和(プラスの数)のみを事前に求めておいて、
最後に反転する位置を全部試してます。