Submission #66118025

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from collections import deque
import sys
def sliding_window_max_sum(A, k):
    dq = deque()
    total = 0
    for i in range(len(A)):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and A[dq[-1]] <= A[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            total += A[dq[0]]
    return total
def main():
    input = sys.stdin.read
    data = list(map(int, input().split()))
    N = data[0]
    A = data[1:]
    for k in range(1, N + 1):
        print(sliding_window_max_sum(A, k))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import deque
import sys
def sliding_window_max_sum(A, k):
    dq = deque()
    total = 0
    for i in range(len(A)):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and A[dq[-1]] <= A[i]:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            total += A[dq[0]]
    return total
def main():
    input = sys.stdin.read
    data = list(map(int, input().split()))
    N = data[0]
    A = data[1:]
    for k in range(1, N + 1):
        print(sliding_window_max_sum(A, k))
if __name__ == "__main__":
    main()

Submission Info

Judge Result