【pythonでABC189を解説】C - Mandarin Orange

問題概要

問題ページ

C - Mandarin Orange

問題ページへ移動する

問題文

高橋君の前に \(N\) 枚の皿が一列に並べられており、左から \(i\) 番目の皿には \(A_i\) 個のみかんが置かれています。

高橋君は次の \(3\) つの条件を全て満たすような整数の組 \((l,r,x)\) を \(1\) つ選びます。

• \(1\leq l \leq r \leq N\)
• \(1 \le x\)
• \(l\) 以上 \(r\) 以下の全ての整数 \(i\) について、\(x \le A_i\)

その後、高橋君は \(l\) 番目から \(r\) 番目まで (両端を含む) の全ての皿からみかんを \(x\) 個ずつ取って食べます。

整数の組 \((l,r,x)\) を適切に選んだとき、高橋君は最大で何個のみかんを食べることができますか。

制約

• 入力は全て整数
• \(1 \leq N \leq 10^4\)
• \(1 \leq A_i \leq 10^5\)

問題の考察

ACコード

import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    a = list(map(int, input().rstrip('\n').split()))
    mx = 0
    for i in range(n):
        mn = a[i]
        for j in range(i, n):
            mn = min(mn, a[j])
            mx = max(mx, (j - i + 1) * mn)
    print(mx)


if __name__ == '__main__':
    solve()