[ABC240F] Sum Sum Max を Pythonで解く

https://atcoder.jp/contests/abc240/tasks/abc240_f

考え方

一般的にはそれほど難問とは扱われていませんが、私はすごく苦手で混乱してしまったので、備忘録として残しておきます。まずは、入力例1の最初のテストケースで考えてみます。
数列 $C$ の値が同じ数字となっているブロックをひとかたまりとしてみると、ブロックの最後の数は、$x$ , $y$ の値で下図のように変化します。これらを $b_i$, $a_i$ とします。

$A$ が単調増加または単調減少のときには、ブロックの最後の数 $a_i$ は最大値の候補となります。また、これらの端点以外にもブロック途中で最大値となる場合があるのですが、$B$ のグラフを考えると、$b_i$ が正で、$x$ が負のとき、$B$ は減少して $0$ をまたぐ場合があり、このとき、$A$ は極大値をとります。

このような $A$ の極大値を求めるには、どのタイミングで $B$ が $0$ をまたぐのかを計算する必要があります。

上図のように考えると、極大値を求めることができます。あとは、候補となる値で最大のものを求めれば良いです。$A$ の初項は、$x_1$ となりますが、この値も最大値の候補となることを忘れないように注意しましょう。

実装メモ

def solve():
    N,M = map(int,input().split())
    a,b = 0,0
    
    for n in range(N):
        x,y = map(int,input().split())
        if n == 0:
            ans = x

        if b>0 and x<0:
            k = b//(-x)
            if k < y:
                ans = max(ans, a+x*k*(k+1)//2+b*k)

        a += x*y*(y+1)//2+b*y
        b += x*y
        ans = max(ans,a)

    return ans

answers = []
T = int(input())
for t in range(T):
    answers.append(solve())

print(*answers,sep="\n")

理解すると、実装自体はそれほど大変ではありません。