Problem:


Score : 700 points

Problem Statement

There are N panels arranged in a row in Takahashi's house, numbered 1 through N. The i-th panel has a number A_i written on it. Takahashi is playing by throwing balls at these panels.

Takahashi threw a ball K times. Let the panel hit by a boll in the i-th throw be panel p_i. He set the score for the i-th throw as i \times A_{p_i}.

He was about to calculate the total score for his throws, when he realized that he forgot the panels hit by balls, p_1,p_2,...,p_K. The only fact he remembers is that for every i (1 ≦ i ≦ K-1), 1 ≦ p_{i+1}-p_i ≦ M holds. Based on this fact, find the maximum possible total score for his throws.

Constraints

1 ≦ M ≦ N ≦ 100,000

1 ≦ K ≦ min(300,N)

1 ≦ A_i ≦ 10^{9}

Partial Scores

In the test set worth 100 points, M = N.

In the test set worth another 200 points, N ≦ 300 and K ≦ 30.

In the test set worth another 300 points, K ≦ 30.

Input

The input is given from Standard Input in the following format:

N M K
A_1 A_2 … A_N

Output

Print the maximum possible total score for Takahashi's throws.

Sample Input 1

5 2 3
10 2 8 10 2

Sample Output 1

56

The total score is maximized when panels 1,3 and 4 are hit, in this order.

Sample Input 2

5 5 2
5 2 10 5 9

Sample Output 2

28

This case satisfies the additional constraint M = N for a partial score.

Sample Input 3

10 3 5
3 7 2 6 9 4 8 5 1 1000000000

Sample Output 3

5000000078



Sample input:
5 2 3
10 2 8 10 2


Sample output:
56

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def main(A, M, K):
    # 右端ごとの最高得点を管理。まずは 1 回目。
    INF = 1 << 60
    dp = A.copy()

    q = np.empty(len(A) + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def pop(q):
        q[0] += 1
        return q[q[0] - 1]

    def is_empty(q):
        return q[0] == q[1]

    for k in range(2, K + 1):
        newdp = np.full_like(A, -INF)
        q[:2] = 2, 2
        for i in range(len(A)):
            if not is_empty(q):
                x = dp[q[q[0]]]
                newdp[i] = x + A[i] * k
            x = dp[i]
            while not is_empty(q) and dp[q[q[1] - 1]] < x:
                pop(q)
            push(q, i)
            while q[q[0]] <= i - M:
                q[0] += 1
        dp = newdp
    return dp.max()

N, M, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(A, M, K))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def main(A, M, K):
    # 右端ごとの最高得点を管理。まずは 1 回目。
    INF = 1 << 60
    dp = A.copy()

    q = np.empty(len(A) + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def pop(q):
        q[0] += 1
        return q[q[0] - 1]

    def is_empty(q):
        return q[0] == q[1]

    for k in range(2, K + 1):
        newdp = np.full_like(A, -INF)
        q[:2] = 2, 2
        for i in range(len(A)):
            if not is_empty(q):
                x = dp[q[q[0]]]
                newdp[i] = x + A[i] * k
            x = dp[i]
            while not is_empty(q) and dp[q[q[1] - 1]] < x:
                pop(q)
            push(q, i)
            while q[q[0]] < i - M:
                q[0] += 1
        dp = newdp
    return dp.max()

N, M, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(A, M, K))

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

#@njit((i8[:], i8, i8), cache=True)
def main(A, M, K):
    # 右端ごとの最高得点を管理。まずは 1 回目。
    INF = 1 << 60
    dp = A.copy()

    q = np.empty(len(A) + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def pop(q):
        q[0] += 1
        return q[q[0] - 1]

    def is_empty(q):
        return q[0] == q[1]

    for k in range(2, K + 1):
        newdp = np.full_like(A, -INF)
        q[:2] = 2, 2
        for i in range(len(A)):
            if not is_empty(q):
                x = dp[q[q[0]]]
                newdp[i] = x + A[i] * k
            x = dp[i]
            while not is_empty(q) and dp[q[q[1] - 1]] < x:
                pop(q)
            push(q, i)
            while q[q[0]] < i - M:
                q[0] += 1
        dp = newdp
    return dp.max()

N, M, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(A, M, K))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = [0] * (N + 1)
for j in range(K):
    newDP = [0] * (N + 1)
    que = deque()  # val, index
    for i in range(j, N - K + j + 1):
        while que and que[-1][0] < dp[i]:
            que.pop()
        while que and que[0][1] < i - M:
            que.popleft()
        que.append((dp[i], i))
        newDP[i+1] = que[0][0] + (j+1)*A[i]
    dp = newDP

print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = [0] * (N + 1)
for j in range(K):
    newDP = [0] * (N + 1)
    que = deque()  # val, index
    for i in range(j, N - K + j + 1):
        while que and que[-1][0] < dp[i]:
            que.pop()
        que.append((dp[i], i))
        newDP[i+1] = que[0][0] + (j+1)*A[i]
        while que and que[0][1] < i - M:
            que.popleft()
    dp = newDP

print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = [0] * (N + 1)
for j in range(K):
    newDP = [0] * (N + 1)
    que = deque()  # val, index
    for i in range(j, N - K + j + 1):
        while que and que[-1][0] < dp[i]:
            que.pop()
        que.append((dp[i], i))
        while que and que[0][1] < i - M:
            que.popleft()
        newDP[i+1] = que[0][0] + (j+1)*A[i]
    dp = newDP

print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = [0] * (N + 1)
for j in range(K):
    newDP = [0] * (N + 1)
    que = deque()  # val, index
    for i in range(j, N - K + j + 1):
        while que and que[-1][0] <= dp[i]:
            que.pop()
        que.append((dp[i], i))
        while que and que[0][1] < i - M:
            que.popleft()
        newDP[i+1] = que[0][0] + (j+1)*A[i]
    dp = newDP

print(max(dp))

Submission status: Wrong Answer

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = A.copy()
for j in range(2, K + 1):
    newDP = [0] * N
    newDP[0] = dp[0]
    memo = deque()  # score, index
    for i, score in enumerate(dp[:-1]):
        while memo and memo[-1][0] <= score:
            memo.pop()
        memo.append((score, i))
        newDP[i + 1] = memo[0][0] + j * A[i + 1]
        while memo and memo[0][1] <= i - M:
            memo.popleft()
    dp = newDP

print(max(dp))

Submission status: Wrong Answer

Solution code:
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
    for k in range(K-1):
        que = deque()
        for i, a in enumerate(S[:-1]):
            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()

Submission status: Wrong Answer

Solution code:
from sys import stderr

def reads():
  return [int(x) for x in input().split()]

N, M, K = reads()
A = reads()

dp = [[0] * N, list(A)]
deq = [0] * N
for j in range(2, K+1):
  l = r = 0
  b = j & 1
  prev = dp[1-b]; curr = dp[b]
  for i in range(N):
    # pop
    while l < r and deq[l] < i-M:
      l += 1
    # max
    curr[i] = (j * A[i] + prev[deq[l]]) if l < r else 0
    # append
    while l < r and prev[deq[r-1]] <= prev[i]:
      r -= 1
    deq[r] = i; r += 1

print(max(dp[K & 1]))

Submission status: Wrong Answer

Solution code:
from sys import stderr
from collections import deque

def reads():
  return [int(x) for x in input().split()]

INF = 1 << 31

N, M, K = reads()
A = reads()

dp = A
for j in range(2, K+1):
  deq = deque()
  q = [-INF] * N
  for i in range(N):
    # pop
    while deq and deq[0] < i-M:
      deq.popleft()
    # max
    q[i] = (j * A[i] + dp[deq[0]]) if deq else -INF
    # append
    while deq and dp[deq[-1]] <= dp[i]:
      deq.pop()
    deq.append(i)
  dp = q

print(max(dp))

Submission status: Wrong Answer

Solution code:
from sys import stderr
from collections import deque

def reads():
  return [int(x) for x in input().split()]

INF = 1 << 31

N, M, K = reads()
A = reads()

dp = A
print(dp)
for j in range(2, K+1):
  deq = deque()
  q = [-INF] * N
  for i in range(N):
    # pop
    while deq and deq[0] < i-M:
      deq.popleft()
    # max
    q[i] = (j * A[i] + dp[deq[0]]) if deq else -INF
    # append
    while deq and dp[deq[-1]] <= dp[i]:
      deq.pop()
    deq.append(i)
    print(deq)
  dp = q
  print(dp)

print(max(dp))

Submission status: Wrong Answer

Solution code:
from sys import stderr
from collections import deque

def reads():
  return [int(x) for x in input().split()]

INF = 1 << 31

def _max(xs):
  try:
    return max(xs)
  except:
    return -INF

class SlideMax:
  def __init__(self, xs):
    self.array = xs
    self.deq = deque()

  def append(self, i):
    xs = self.array
    while self.deq and xs[self.deq[-1]] <= xs[i]:
      self.deq.pop()
    self.deq.append(i)

  def max(self):
    xs = self.array
    return xs[self.deq[0]] if len(self.deq) > 0 else -INF

  def pop_until(self, i):
    while self.deq and self.deq[0] < i:
      self.deq.popleft()

N, M, K = reads()
A = reads()

dp = A
for j in range(2, K+1):
  deq = SlideMax(dp)
  q = [-INF] * N
  for i in range(N):
    deq.pop_until(i-M)
    q[i] = j * A[i] + deq.max()
    # q[i] = j * A[i] + _max(dp[k] for k in range(max(i-M, 0), i))
    deq.append(i)
  dp = q

print(max(dp))

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]
if M==N:
    dp=[[0]*(N+1) for i in range(K+1)]
    for i in range(1,N+1):
        for k in range(1,min(i,K)+1):
            dp[k][i] = max(dp[k][i-1],dp[k-1][i-1]+A[i-1]*k)
    #print(dp)
    print(dp[K][N])
    sys.exit()
if N>310:
    print(0)
    sys.exit()
dp=[[0]*(K+1) for i in range(N+1)]
ans=0
for i in range(1,N+1):
    for k in range(1,min(i,K)+1):
        for j in range(max(0,i-M),i):
            dp[i][k]=max(dp[i][k],dp[j][k-1]+A[i-1]*k)
ans=0
#print(dp)
for i in range(N+1):
    ans=max(ans,dp[i][K])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]
if M==N:
    dp=[[0]*(N+1) for i in range(K+1)]
    for i in range(1,N+1):
        for k in range(1,min(i,K)+1):
            dp[k][i] = max(dp[k][i-1],dp[k-1][i-1]+A[i-1]*k)
    #print(dp)
    print(dp[K][N])
    sys.exit()
if N>310:
    print(0)
    sys.exit()
dp=[[0]*(K+1) for i in range(N+1)]
ans=0
for i in range(1,N+1):
    for k in range(1,K+1):
        for j in range(max(0,i-M),i):
            dp[i][k]=max(dp[i][k],dp[j][k-1]+A[i-1]*k)
ans=0
for i in range(N+1):
    ans=max(ans,dp[i][K])
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]
if M!=N:
    print(0)
    sys.exit()
dp=[[0]*(N+1) for i in range(K+1)]
for i in range(1,N+1):
    for k in range(1,min(i,K)+1):
        dp[k][i] = max(dp[k][i-1],dp[k-1][i-1]+A[i-1]*k)
#print(dp)
print(dp[K][N])

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]
if M!=N:
    print(0)
    sys.exit()
dp=[[0]*(N+1) for i in range(K+1)]
for i in range(1,N+1):
    for k in range(1,K+1):
        dp[k][i] = max(dp[k][i-1],dp[k-1][i-1]+A[i-1]*k)
#print(dp)
print(dp[K][N])

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappop,heappush
N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]
if K>31:
    print(0)
    sys.exit()
dp=[[0]*(N+1) for i in range(K+1)]
for i in range(1,N+1):
    for k in range(1,K+1):
        dp[k][i] = max(dp[k][i-1],dp[k-1][i-1]+A[i-1]*k)
#print(dp)
print(dp[K][N])

Submission status: Wrong Answer

Solution code:
st = input().split()
sA = input().split()
N = int(st[0])
M = int(st[1])
K = int(st[2])
A = []
for i in range(N):
    A.append(int(sA[i]))

def solve(N,M,K,A):
    ret = 0
    if 1:
        Al = [(i,A[i]) for i in range(N)]
        sAl = sorted(Al,key=lambda x:x[1],reverse=True)
        aAl = []
        for i in range(K):
            aAl.append(sAl[i])
        saAl = sorted(aAl)
        for i in range(K):
            ret += saAl[i][1] * (i+1)
#    else:
#        for i in N:
    return ret

print(solve(N,M,K,A))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys

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

if M == N:
    dp = [[-1 for i in range(300)] for j in range(10**5)]
    def rec(k, i):
        if dp[i][k] > 0:
            return dp[i][k]
        if N-i < k:
            return - float('inf')
        if K == k:
            return K * max(A[i:])
        if N == i:
            return - float('inf')
        result = max(rec(k+1, i+1) + k * A[i],
                     rec(k, i+1))
        dp[i][k] = result
        return result
    print(rec(0, 0))
else:
    print(0)
    sys.exit()

Submission status: Wrong Answer

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

INF = 10**10

(N, M, K) = reads()
A = [None] + reads()

d = defaultdict(lambda: -INF)

d[0, 0] = 0

for n in range(1,N+1):
  k = 1
  # print("aa")
  d[n,1] = A[n]
  # print("d[{1},{2}] = {0}".format(d[n,k], n, k))


# d[n, k]: n枚目のパネルで丁度k枚とる点数の最大値
for k in range(2,K+1):
  for n in range(1,N+1):
    d[n, k] = k * A[n] + max(d[n-i, k-1] for i in range(1,M+1))
    # print("d[{1},{2}] = {0}".format(d[n,k], n, k))


print(max(d[n, K] for n in range(N+1)))

Submission status: Wrong Answer

Solution code:
st = input().split()
sA = input().split()
N = int(st[0])
M = int(st[1])
K = int(st[2])
A = []
for i in range(N):
    A.append(int(sA[i]))

ret = 0
if M == N:
    Al = [(i,A[i]) for i in range(N)]
    sAl = sorted(Al,key=lambda x:x[1],reverse=True)
    aAl = []
    for i in range(K):
        aAl.append(sAl[i])
    saAl = sorted(aAl)
    for i in range(K):
        ret += saAl[i][1] * (i+1)

print(ret)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys

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

if M == N:
    A = sorted(A)
    score = 0
    for i in range(1, K+1):
        # print(A[-K+i-1])
        score += i * A[-K+i-1]
    print(score)
else:
    print(0)
    sys.exit()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import sys

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

if M == N:
    A = sorted(A)
    score = 0
    for k in range(1, K+1):
        score += k * A[-k]
    print(score)
else:
    print(0)
    sys.exit()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
from sys import stderr

def reads():
  return [int(x) for x in input().split()]

INF = 1 << 63

N, M, K = reads()
A = reads()

dp = A
for j in range(2, K+1):
  deq = [0] * N; l = r = 0
  q = [-INF] * N
  for i in range(N):
    # pop
    while l < r and deq[l] < i-M:
      l += 1
    # max
    q[i] = j * A[i] + (dp[deq[l]] if l < r else -INF)
    # append
    while l < r and dp[deq[r-1]] <= dp[i]:
      r -= 1
    deq[r] = i; r += 1
  dp = q

print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def f(A,N,M):
    H=deque()
    H.append(0)
    L=[0]*N
    for i in range(1,min(M+1,N)):
        L[i] = H[0]
        while len(H)>0 and A[H[-1]]<=A[i]:
            H.pop()
        H.append(i)
    for i in range(M+1,N):
        if H[0]<i-M:
            H.popleft()
        L[i] = H[0]
        while len(H)>0 and A[H[-1]]<=A[i]:
            H.pop()
        H.append(i)
    return [0]+[A[L[a]] for a in range(1,N)]


N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]

dp=[0]*(N+1)
ans=0
for k in range(1,K + 1):
    B = f(dp,N+1,M)
    ndp = [0]*(N+1)
    for i in range(k,N+1):
        ndp[i]=B[i]+k*A[i-1]
    dp=ndp

for i in range(N+1):
    ans=max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def f(A,N,M):
    H=deque()
    H.append((A[0],0))
    L=[0]*N
    for i in range(1,min(M+1,N)):
        L[i] = H[0][0]
        while len(H)>0 and H[-1][0]<=A[i]:
            H.pop()
        H.append((A[i],i))
    for i in range(M+1,N):
        if H[0][1]<i-M:
            H.popleft()
        L[i] = H[0][0]
        while len(H)>0 and H[-1][0]<=A[i]:
            H.pop()
        H.append((A[i],i))
    return L

N,M,K=map(int,input().split())
A=[int(i) for i in input().split()]

dp=[0]*(N+1)
ans=0
for k in range(1,K + 1):
    B = f(dp,N+1,M)
    ndp = [0]*(N+1)
    #print(B)
    for i in range(k,N+1):
        ndp[i]=B[i]+k*A[i-1]
    dp=ndp
    #print(dp)

for i in range(N+1):
    ans=max(dp)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, setrecursionlimit
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

setrecursionlimit(1000000)

INF = 10**10

(N, M, K) = reads()
A = [None] + reads()

if N == M:
  print(sum(i * A[i] for i in range(N+1)))

d = defaultdict(lambda: -INF)

d[0, 0] = 0

for n in range(1,N+1):
  k = 1
  # print("aa")
  d[n,1] = A[n]
  # print("d[{1},{2}] = {0}".format(d[n,k], n, k))


# d[n, k]: n枚目のパネルで丁度k枚とる点数の最大値
for k in range(2,K+1):
  for n in range(1,N+1):
    d[n, k] = k * A[n] + max(d[n-i, k-1] for i in range(1,M+1))
    # print("d[{1},{2}] = {0}".format(d[n,k], n, k))


print(max(d[n, K] for n in range(N+1)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8, i8), cache=True)
def main(A, M, K):
    # 右端ごとの最高得点を管理。まずは 1 回目。
    INF = 1 << 60
    dp = A.copy()

    q = np.empty(len(A) + 100, np.int32)
    q[:2] = 2, 2

    def push(q, x):
        q[q[1]] = x
        q[1] += 1

    def is_empty(q):
        return q[0] == q[1]

    for k in range(2, K + 1):
        newdp = np.full_like(A, -INF)
        q[:2] = 2, 2
        for i in range(len(A)):
            if not is_empty(q):
                x = dp[q[q[0]]]
                newdp[i] = x + A[i] * k
            x = dp[i]
            while not is_empty(q) and dp[q[q[1] - 1]] < x:
                q[1] -= 1
            push(q, i)
            while q[q[0]] <= i - M:
                q[0] += 1
        dp = newdp
    return dp.max()

N, M, K = map(int, readline().split())
A = np.array(read().split(), np.int64)

print(main(A, M, K))

Submission status: Accepted

Solution code:
from collections import deque
N, M, K = map(int, input().split())
A = list(map(int, input().split()))

#dp[i][j]: i番目の的をj回目にあてた時のpointの最大値
dp = [0] * (N + 1)
for j in range(K):
    newDP = [0] * (N + 1)
    que = deque()  # val, index
    for i in range(j, N - K + j + 1):
        while que and que[-1][0] < dp[i]:
            que.pop()
        que.append((dp[i], i))
        while que and que[0][1] <= i - M:
            que.popleft()
        newDP[i+1] = que[0][0] + (j+1)*A[i]
    dp = newDP

print(max(dp))

Submission status: Accepted

Solution code:
from sys import stderr

def reads():
  return [int(x) for x in input().split()]

N, M, K = reads()
A = reads()

dp = [[0] * N, list(A)]
deq = [0] * N
for j in range(2, K+1):
  l = r = 0
  b = j & 1
  prev = dp[1-b]; curr = dp[b]
  for i in range(N):
    # pop
    while l < r and deq[l] < i-M:
      l += 1
    # max
    curr[i] = (j * A[i] + prev[deq[l]]) if (i >= j-1 and l < r) else 0
    # append
    while l < r and prev[deq[r-1]] <= prev[i]:
      r -= 1
    deq[r] = i; r += 1

print(max(dp[K & 1]))