ARC120-A Max Add

問題へのリンク

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("3");
            WillReturn.Add("1 2 3");
            //2
            //8
            //19
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        List<long> RunSum1 = AArr.ToList();
        List<long> RunMaxList = AArr.ToList();

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I > 0) RunSum1[I] += RunSum1[I - 1];
            if (I > 0) RunMaxList[I] = Math.Max(RunMaxList[I], RunMaxList[I - 1]);
        }

        List<long> RunSum2 = RunSum1.ToList();
        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            if (I > 0) RunSum2[I] += RunSum2[I - 1];
        }

        for (int I = 0; I <= AArr.GetUpperBound(0); I++) {
            Console.WriteLine(RunMaxList[I] * (I + 1) + RunSum2[I]);
        }
    }
}

解説

A B C D
という数列で考え、max(A,B,C,D)をMとおきます。
そして、数列の各値を順に考えると下記になります。

1項目は M+A
2項目は M+A+B
3項目は M+A+B+C
4項目は M+A+B+C+D

1項目までの和は 1*M + 1*A
2項目までの和は 2*M + 2*A + 1*B
3項目までの和は 3*M + 3*A + 2*B + 1*C
4項目までの和は 4*M + 4*A + 3*B + 2*C + 1*D

M以外の和は、累積和の累積和を求めることで分かります。
Mの和は、累積Maxから求めることができます。