2531. 회전 초밥, 15961. 회전 초밥

Carnival7 2023. 1. 28. 22:52

https://www.acmicpc.net/problem/2531

2531번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤

www.acmicpc.net

https://www.acmicpc.net/problem/15961

15961번: 회전 초밥

첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 3,000,000, 2 ≤ d ≤ 3,000, 2

www.acmicpc.net

import sys
input=sys.stdin.readline

n,d,k,c=map(int,input().split())
a=[]
for i in range(n):
    a.append(int(input()))

b=[0]*(d+1)
b[c]=1
cnt=1
ans=0

for i in range(k):
    if b[a[i]]==0:
        cnt+=1
    b[a[i]]+=1
ans=max(ans,cnt)

for i in range(k,n):
    j=i-k
    if b[a[i]]==0:
        cnt+=1
    b[a[i]] += 1
    b[a[j]] -= 1
    if b[a[j]] == 0:
        cnt -= 1
    ans=max(ans,cnt)

a=a[n-k+1:]+a[:n-k+1]

b=[0]*(d+1)
b[c]=1
cnt=1

for i in range(k):
    if b[a[i]]==0:
        cnt+=1
    b[a[i]]+=1
ans=max(ans,cnt)

for i in range(k,k+(n-1-k)):
    j=i-k
    if b[a[i]]==0:
        cnt+=1
    b[a[i]] += 1
    b[a[j]] -= 1
    if b[a[j]] == 0:
        cnt -= 1
    ans=max(ans,cnt)

print(ans)