Submission #37167357

Source Code Expand

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


# 3次元配列作る
dp = [[-1]*(D) for i in range(N+1)]
for i in range(N+1):
    for j in range(D):
        dp[i][j] = [-1]*(K+1)
#print(dp)
dp[0][0][0] = 0
# 配る
for i in range(N):#An
    for j in range(D):#あまり
        for k in range(K+1):#選択した数
            # 存在しないものはパス
            if dp[i][j][k] == -1:
                continue
            # 選ばない場合
            dp[i+1][j][k] = max(dp[i+1][j][k], dp[i][j][k])
            # もう選べない
            if k == K:
                continue

            # 選ぶとき
            a = A[i]
            tmp = dp[i][j][k]+a
            dp[i+1][tmp%D][k+1] = max(dp[i+1][tmp%D][k+1], tmp)

#print(dp)
print(dp[N][0][K])

Submission Info

Submission Time
Task D - Max Multiple
User te1229
Language PyPy3 (7.3.0)
Score 400
Code Size 825 Byte
Status AC
Exec Time 99 ms
Memory 81336 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 400 / 400
Status
AC × 2
AC × 29
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt
All 00_sample_00.txt, 00_sample_01.txt, 01_srnd_00.txt, 01_srnd_01.txt, 01_srnd_02.txt, 01_srnd_03.txt, 01_srnd_04.txt, 01_srnd_05.txt, 01_srnd_06.txt, 01_srnd_07.txt, 02_rnd_00.txt, 02_rnd_01.txt, 02_rnd_02.txt, 02_rnd_03.txt, 02_rnd_04.txt, 02_rnd_05.txt, 02_rnd_06.txt, 02_rnd_07.txt, 03_max_00.txt, 03_max_01.txt, 03_max_02.txt, 04_obvious_00.txt, 04_obvious_01.txt, 04_obvious_02.txt, 04_obvious_03.txt, 05_hand_00.txt, 05_hand_01.txt, 05_hand_02.txt, 05_hand_03.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 65 ms 61944 KiB
00_sample_01.txt AC 48 ms 61964 KiB
01_srnd_00.txt AC 48 ms 61860 KiB
01_srnd_01.txt AC 52 ms 62080 KiB
01_srnd_02.txt AC 54 ms 61940 KiB
01_srnd_03.txt AC 49 ms 61884 KiB
01_srnd_04.txt AC 52 ms 62200 KiB
01_srnd_05.txt AC 52 ms 62188 KiB
01_srnd_06.txt AC 52 ms 62036 KiB
01_srnd_07.txt AC 49 ms 64020 KiB
02_rnd_00.txt AC 90 ms 77920 KiB
02_rnd_01.txt AC 82 ms 74720 KiB
02_rnd_02.txt AC 93 ms 78468 KiB
02_rnd_03.txt AC 92 ms 78336 KiB
02_rnd_04.txt AC 81 ms 75332 KiB
02_rnd_05.txt AC 78 ms 74816 KiB
02_rnd_06.txt AC 60 ms 68192 KiB
02_rnd_07.txt AC 99 ms 79108 KiB
03_max_00.txt AC 79 ms 81324 KiB
03_max_01.txt AC 82 ms 81016 KiB
03_max_02.txt AC 79 ms 81336 KiB
04_obvious_00.txt AC 63 ms 70384 KiB
04_obvious_01.txt AC 55 ms 67744 KiB
04_obvious_02.txt AC 53 ms 65536 KiB
04_obvious_03.txt AC 65 ms 70380 KiB
05_hand_00.txt AC 97 ms 78732 KiB
05_hand_01.txt AC 79 ms 76492 KiB
05_hand_02.txt AC 78 ms 76588 KiB
05_hand_03.txt AC 81 ms 76616 KiB