Submission #1797899


Source Code Expand

def d_supplement(N, M, F):
    """
    N:サプリメントの数
    M:サプリメントの味の種類
    F:要素iの値はi番目のサプリメントの味(1-origin)
    """
    MOD = 10**9 + 7

    """
    dp[i] = dp[i-1] + dp[i-2] + ... + dp[k]
    kは F[j+1], F[j+2], ..., F[i] をすべて1日で摂取できるようなjのうち最小のもの。
    """
    dp = [0] * (N + 1)
    dp[0] = 1  # 最初は"何も食べていない"1通り

    num = [0] * (M + 1)  # 尺取の区間内での、サプリの味ごとの個数
    left = 0  # 上のdpのコメントにおけるkの役割
    sum = dp[0]

    for i in range(N):
        num[F[i]] += 1
        # 区間内に含まれる同じ味のサプリメント個数が1つになるまでdpの左端を縮める
        while num[F[i]] > 1:
            num[F[left]] -= 1
            sum -= dp[left]
            if sum < 0:
                sum += MOD
            sum %= MOD
            left += 1
        dp[i + 1] = sum
        sum += dp[i + 1]
        sum %= MOD
    return dp[-1]
  
N,M = [int(i) for i in input().split()]
F = [int(input()) for _ in range(N)]
print(d_supplement(N, M, F))

Submission Info

Submission Time
Task D - サプリメント
User kenseiQ
Language Python (3.4.3)
Score 100
Code Size 1192 Byte
Status AC
Exec Time 248 ms
Memory 11820 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 2
AC × 22
AC × 42
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask1-16.txt, subtask1-17.txt, subtask1-18.txt, subtask1-19.txt, subtask1-20.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt, subtask2-16.txt, subtask2-17.txt, subtask2-18.txt, subtask2-19.txt, subtask2-20.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 17 ms 3064 KB
subtask0-sample02.txt AC 17 ms 3064 KB
subtask1-01.txt AC 20 ms 3064 KB
subtask1-02.txt AC 21 ms 3188 KB
subtask1-03.txt AC 21 ms 3064 KB
subtask1-04.txt AC 22 ms 3188 KB
subtask1-05.txt AC 24 ms 3064 KB
subtask1-06.txt AC 23 ms 3316 KB
subtask1-07.txt AC 23 ms 3316 KB
subtask1-08.txt AC 25 ms 3316 KB
subtask1-09.txt AC 27 ms 3188 KB
subtask1-10.txt AC 27 ms 3188 KB
subtask1-11.txt AC 27 ms 3188 KB
subtask1-12.txt AC 27 ms 3316 KB
subtask1-13.txt AC 28 ms 3316 KB
subtask1-14.txt AC 28 ms 3344 KB
subtask1-15.txt AC 28 ms 3316 KB
subtask1-16.txt AC 28 ms 3444 KB
subtask1-17.txt AC 28 ms 3444 KB
subtask1-18.txt AC 26 ms 3444 KB
subtask1-19.txt AC 28 ms 3316 KB
subtask1-20.txt AC 28 ms 3316 KB
subtask2-01.txt AC 59 ms 4596 KB
subtask2-02.txt AC 104 ms 5780 KB
subtask2-03.txt AC 152 ms 8620 KB
subtask2-04.txt AC 189 ms 10152 KB
subtask2-05.txt AC 230 ms 7836 KB
subtask2-06.txt AC 238 ms 7800 KB
subtask2-07.txt AC 235 ms 7804 KB
subtask2-08.txt AC 248 ms 10624 KB
subtask2-09.txt AC 235 ms 10984 KB
subtask2-10.txt AC 234 ms 11820 KB
subtask2-11.txt AC 239 ms 11808 KB
subtask2-12.txt AC 225 ms 11772 KB
subtask2-13.txt AC 242 ms 11820 KB
subtask2-14.txt AC 243 ms 10192 KB
subtask2-15.txt AC 226 ms 11816 KB
subtask2-16.txt AC 235 ms 10128 KB
subtask2-17.txt AC 236 ms 11820 KB
subtask2-18.txt AC 220 ms 11812 KB
subtask2-19.txt AC 233 ms 10144 KB
subtask2-20.txt AC 224 ms 11816 KB