Submission #30181308

Source Code Expand

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [[0] * n for i in range(n)]
answer = 0
for i in range(n):
    prefix_max = a[i]
    for x in range(0, min(i, (i + 1) - k + 1)):
        prefix_max = max(prefix_max, dp[x][i])
    for j in range(i + 1, n):
        if 0 <= j - k < i:
            prefix_max = max(prefix_max, dp[j - k][i])
        dp[i][j] = prefix_max + a[j]
        answer = max(answer, dp[i][j])
print(answer)

Submission Info

Submission Time
Task D - 飴 2 (Candies 2)
User Pro_ktmr
Language PyPy3 (7.3.0)
Score 100
Code Size 463 Byte
Status AC
Exec Time 226 ms
Memory 144868 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4
Score / Max Score 0 / 0 4 / 4 19 / 19 47 / 47 30 / 30
Status
AC × 4
AC × 20
AC × 23
AC × 46
AC × 96
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Subtask1 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt
Subtask2 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt
Subtask3 sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 03-26.txt
Subtask4 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, 02-17.txt, 02-18.txt, 02-19.txt, 03-01.txt, 03-02.txt, 03-03.txt, 03-04.txt, 03-05.txt, 03-06.txt, 03-07.txt, 03-08.txt, 03-09.txt, 03-10.txt, 03-11.txt, 03-12.txt, 03-13.txt, 03-14.txt, 03-15.txt, 03-16.txt, 03-17.txt, 03-18.txt, 03-19.txt, 03-20.txt, 03-21.txt, 03-22.txt, 03-23.txt, 03-24.txt, 03-25.txt, 03-26.txt, 04-01.txt, 04-02.txt, 04-03.txt, 04-04.txt, 04-05.txt, 04-06.txt, 04-07.txt, 04-08.txt, 04-09.txt, 04-10.txt, 04-11.txt, 04-12.txt, 04-13.txt, 04-14.txt, 04-15.txt, 04-16.txt, 04-17.txt, 04-18.txt, 04-19.txt, 04-20.txt, 04-21.txt, 04-22.txt, 04-23.txt, 04-24.txt, 04-25.txt, 04-26.txt, 04-27.txt, 04-28.txt, 04-29.txt, 04-30.txt, 04-31.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 125 ms 61620 KiB
01-02.txt AC 50 ms 61812 KiB
01-03.txt AC 52 ms 61764 KiB
01-04.txt AC 53 ms 61828 KiB
01-05.txt AC 53 ms 61616 KiB
01-06.txt AC 49 ms 61760 KiB
01-07.txt AC 50 ms 61784 KiB
01-08.txt AC 50 ms 61756 KiB
01-09.txt AC 49 ms 61680 KiB
01-10.txt AC 52 ms 61748 KiB
01-11.txt AC 54 ms 61632 KiB
01-12.txt AC 53 ms 61616 KiB
01-13.txt AC 51 ms 61388 KiB
01-14.txt AC 53 ms 61724 KiB
01-15.txt AC 55 ms 61696 KiB
01-16.txt AC 51 ms 61688 KiB
02-01.txt AC 218 ms 144356 KiB
02-02.txt AC 219 ms 144572 KiB
02-03.txt AC 218 ms 144548 KiB
02-04.txt AC 215 ms 144524 KiB
02-05.txt AC 213 ms 144676 KiB
02-06.txt AC 214 ms 144496 KiB
02-07.txt AC 212 ms 144320 KiB
02-08.txt AC 211 ms 144820 KiB
02-09.txt AC 192 ms 144360 KiB
02-10.txt AC 52 ms 61668 KiB
02-11.txt AC 53 ms 61472 KiB
02-12.txt AC 54 ms 61404 KiB
02-13.txt AC 54 ms 61616 KiB
02-14.txt AC 53 ms 61660 KiB
02-15.txt AC 99 ms 86188 KiB
02-16.txt AC 88 ms 79952 KiB
02-17.txt AC 208 ms 143736 KiB
02-18.txt AC 77 ms 75976 KiB
02-19.txt AC 74 ms 73748 KiB
03-01.txt AC 58 ms 66328 KiB
03-02.txt AC 61 ms 67100 KiB
03-03.txt AC 63 ms 68716 KiB
03-04.txt AC 76 ms 74092 KiB
03-05.txt AC 67 ms 70480 KiB
03-06.txt AC 64 ms 68668 KiB
03-07.txt AC 79 ms 73924 KiB
03-08.txt AC 81 ms 74052 KiB
03-09.txt AC 78 ms 73844 KiB
03-10.txt AC 78 ms 74056 KiB
03-11.txt AC 76 ms 73988 KiB
03-12.txt AC 73 ms 73632 KiB
03-13.txt AC 65 ms 66104 KiB
03-14.txt AC 68 ms 71380 KiB
03-15.txt AC 62 ms 67672 KiB
03-16.txt AC 74 ms 73888 KiB
03-17.txt AC 60 ms 66764 KiB
03-18.txt AC 57 ms 64112 KiB
03-19.txt AC 60 ms 67124 KiB
03-20.txt AC 59 ms 66576 KiB
03-21.txt AC 61 ms 67420 KiB
03-22.txt AC 74 ms 74084 KiB
03-23.txt AC 57 ms 64172 KiB
03-24.txt AC 60 ms 67984 KiB
03-25.txt AC 78 ms 74240 KiB
03-26.txt AC 54 ms 61716 KiB
04-01.txt AC 137 ms 134928 KiB
04-02.txt AC 136 ms 134516 KiB
04-03.txt AC 136 ms 135012 KiB
04-04.txt AC 138 ms 134580 KiB
04-05.txt AC 139 ms 134952 KiB
04-06.txt AC 159 ms 144760 KiB
04-07.txt AC 209 ms 144788 KiB
04-08.txt AC 215 ms 144700 KiB
04-09.txt AC 218 ms 144464 KiB
04-10.txt AC 214 ms 144804 KiB
04-11.txt AC 214 ms 144240 KiB
04-12.txt AC 223 ms 144800 KiB
04-13.txt AC 190 ms 144404 KiB
04-14.txt AC 188 ms 144632 KiB
04-15.txt AC 215 ms 144676 KiB
04-16.txt AC 172 ms 144868 KiB
04-17.txt AC 226 ms 144748 KiB
04-18.txt AC 180 ms 144484 KiB
04-19.txt AC 81 ms 74944 KiB
04-20.txt AC 192 ms 134876 KiB
04-21.txt AC 115 ms 99388 KiB
04-22.txt AC 186 ms 126380 KiB
04-23.txt AC 129 ms 108120 KiB
04-24.txt AC 115 ms 89572 KiB
04-25.txt AC 93 ms 80216 KiB
04-26.txt AC 80 ms 77468 KiB
04-27.txt AC 79 ms 76356 KiB
04-28.txt AC 82 ms 81288 KiB
04-29.txt AC 73 ms 78476 KiB
04-30.txt AC 151 ms 111732 KiB
04-31.txt AC 163 ms 116056 KiB
sample-01.txt AC 53 ms 61808 KiB
sample-02.txt AC 54 ms 61572 KiB
sample-03.txt AC 54 ms 61528 KiB
sample-04.txt AC 53 ms 61444 KiB