Submission #65277175

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 Counter
def f(A, D):
    N = len(A)
    cnt = Counter(A)
    if D == 0:
        return N - len(cnt)
    buck= {}
    for v in cnt:
        r = v % D
        buck.setdefault(r, []).append(v)
    def solve(bl):
        w = [cnt[v] for v in bl]
        m = len(w)
        if m == 1:
            return w[0]
        dp0, dp1 = w[0], max(w[0], w[1])
        for i in range(2, m):
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

from collections import Counter

def f(A, D):
    N = len(A)
    cnt = Counter(A)

    if D == 0:
        return N - len(cnt)

    buck= {}
    for v in cnt:
        r = v % D
        buck.setdefault(r, []).append(v)

    def solve(bl):
        w = [cnt[v] for v in bl]
        m = len(w)
        if m == 1:
            return w[0]
        dp0, dp1 = w[0], max(w[0], w[1])
        for i in range(2, m):
            dp0, dp1 = dp1, max(dp1, dp0 + w[i])
        return dp1

    keep = 0
    for vs in buck.values():
        vs.sort()
        bl=[vs[0]]
        for v in vs[1:]:
            if v-bl[-1]==D:
                bl.append(v)
            else:
                keep+=solve(bl)
                bl=[v]
        keep+=solve(bl)

    return N-keep


if __name__ == "__main__":
    import sys
    input = sys.stdin.readline
    N, D = map(int, input().split())
    A = list(map(int, input().split()))
    print(f(A,D))

Submission Info

Judge Result