ABC189 C - Mandarin Orange に痺れた

わ、わからん。
解答 please

うーん、わかったのかな。
とりあえず、分かったつもりになって書いてみた。

MandarinOrange.py

N = int(input())
A = list(map(int,input().split()))

def solv():
    ans = 0
    for l in range(N):
        ref = A[l]
        for r in range(l,N):
            ref = min(ref,A[r])
            ans = max(ans,ref*(r-l+1))
    print(ans)

solv()

Python では間に合わないので
PyPy にしないと通らないのでご注意ください。

---

あれから真っ新で再チャレンジ。
以下の記述で WA。

abc189c_wa.py

def solv():
    N = int(input())
    A = list(map(int,input().split()))
    lis = []
    for i in range(N):
        ref = A[i]
        score = 0
        for j in range(i,N):
            if A[j] < ref:break
            score += ref
        lis.append(score)
    print(max(lis))
solv()

なぜダメなのだろうか。
random_01.txt をダウンロードして
WA/AC を比較してみた。
具体的には、最大合計値、左端、右端を printを使って表示してみる

AC 合計値 901408/ 左端 1429/右端 1445
WA 合計値 125322/ 左端 1429/右端 1431

ご覧のとおりスタート地点は同じだが右端で切れている位置が異なる。
なぜ？
AC/WA には記述に根本的な差がある。

AC : 左端から最小値を更新しながら探索するので、連続してカウントする数を伸ばしている
WA : 左端を最小値とし、最小値以上で連続してないとカウントを止めてしまう

冷静に考えて前者の AC の考え方じゃないと all case を満たした回答が出来ないのではなかろうか？

以上のようにイメージし直すと、
AC の記述に自力で辿り着き、見事 AC となった。