Buggy python submission (verdict: Time Limit Exceeded):
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    def gen(S, k):
        s = t = 0
        it = iter(range(N)).__next__
        i = k-1
        for a, b in zip(S[k-2:], A[k-1:]):
            while s < t and Q1[t-1] <= a:
                t -= 1
            i = it()
            Q0[t] = i-1; Q1[t] = a
            t += 1

            yield Q1[s] + b*k

            if s < t and Q0[s] <= i-M:
                s += 1

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        S[k-1:] = gen(S, k)
    print(max(S))
solve()

Fixed submission:
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

Fixed submission:
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    zeros = [0]*N
    for k in range(K-1):
        que0 = deque()
        que1 = deque()
        T[:k+1] = zeros[:k+1]

        for i in range(k, N-1):
            a = S[i]
            while que1 and que1[-1] <= a:
                que0.pop()
                que1.pop()
            que0.append(i)
            que1.append(a)

            T[i+1] = que1[0] + A[i+1]*(k+2)

            if que0 and que0[0] <= i+1-M:
                que0.popleft()
                que1.popleft()
        S, T = T, S
    print(max(S))
solve()

Fixed submission:
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    zeros = [0]*N
    for k in range(K-1):
        que = deque()
        T[:k+1] = zeros[:k+1]

        for i in range(k, N-1):
            a = S[i]
            while que and que[-1][1] <= a:
                que.pop()
            que.append((i, a))

            T[i+1] = que[0][1] + A[i+1]*(k+2)

            if que and que[0][0] <= i+1-M:
                que.popleft()
        S, T = T, S
    print(max(S))
solve()

Fixed submission:
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    zeros = [0]*N
    for k in range(K-1):
        que = deque()
        T[:k+1] = zeros[:k+1]

        for i in range(k, N-1):
            a = S[i]
            while que and que[-1][1] <= a:
                que.pop()
            que.append((i, a))

            T[i+1] = que[0][1] + A[i+1]*(k+2)

            if que and que[0][0] <= i+1-M:
                que.popleft()
        S, T = T, S
    print(max(S))
solve()

Fixed submission:
import sys
def solve():
    readline = sys.stdin.readline

    N, M, K = map(int, readline().split())
    *A, = map(int, readline().split())

    S = A[:]
    T = [0]*N
    Q0 = [0]*N; Q1 = [0]*N
    for k in range(2, K+1):
        s = t = 0

        for i in range(k-1, N):
            a = S[i-1]
            while s < t and Q1[t-1] <= a:
                t -= 1
            Q0[t] = i-1; Q1[t] = a
            t += 1

            T[i] = Q1[s] + A[i]*k

            if s < t and Q0[s] <= i-M:
                s += 1
        S, T = T, S
    print(max(S))
solve()