Problem:


 
 MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

B - 豪邸と宅配便

Problem Statement

太郎君は豪邸で一人暮らしをしている．
勉強好きの太郎君は，今日も邸内の書斎で勉強をするつもりである．
太郎君は，書斎以外の場所では集中できないので，勉強は必ず書斎で行う．

ところがこの日，太郎君宛の宅配便が $N$ 件届く．$i$ ($1 \leq i \leq N$) 番目の宅配便の届く時刻は $a_i$ である．
配達員を玄関先で待たせるのは心苦しいので，太郎君は宅配便の届く時刻には玄関にいることにした．
豪邸は広いので，書斎と玄関間の移動には片道 $M$ の時間がかかる．

一方で，太郎君はできるだけ長い時間勉強したいと思っている．
時刻 $0$ から時刻 $T$ までで，太郎君が書斎で勉強できる時間の最大値を求めよ．

なお，太郎君は時刻 $0$ には書斎にいて，時刻 $M$ より早く宅配便が届くことはなく，時刻 $T$ より遅く宅配便が届くこともない．
また，太郎君が宅配便を受け取るのにかかる時間は無視できる．

Input

各データセットは 2 行からなる．
1 行目は空白で区切られた 3 つの整数 $N, M, T$ からなる．
これらの整数は，$1 \leq N \leq 100$, $1 \leq M \leq 10{,}000$, $1 \leq T \leq 10{,}000$ を満たす．
2 行目は空白で区切られた $N$ 個の整数 $a_1, a_2, \dots, a_N$ からなる．
各 $a_i$ は $M \leq a_i \leq T$ を満たし，また $a_i < a_{ i + 1 }$ ($1 \leq i < N$) である．

Output

太郎君が勉強できる時間の最大値を表す整数を 1 行に出力せよ．

Sample Input 1

1 1 5
3

Output for the Sample Input 1

3

Sample Input 2

2 1 10
2 7

Output for the Sample Input 2

6

Sample Input 3

2 4 10
6 8

Output for the Sample Input 3

2


Sample input:
1 1 5
3


Sample output:
3

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

a = list(map(int,input().split()))

b = list(map(int,input().split()))

k = [0]*a[2]

su = 0

for i in b:
    for j in range(a[2]):
        if j >= i - a[1] and j <= i + a[1]:
            k[j] += 1
            
            
for i in range(a[2]):
    if k[i] > 0:
        su += 1
        
print(su)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

a = list(map(int,input().split()))

b = list(map(int,input().split()))

k = [0]*a[2]

su = 0

for i in b:
    for j in range(a[2]):
        if j >= i - a[1] and j <= i + a[1]:
            k[j] += 1
            
            
for i in range(a[2]):
    if k[i] == 0:
        su += 1
        
print(su)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

a = list(map(int,input().split()))

b = list(map(int,input().split()))

k = [0]*a[2]
pp = 0
su = 0

for i in b:
    for j in range(a[2]):
        if j >= i - a[1]  + 1 and j <= i + a[1] :
                k[j] += 1
            
for i in range(a[2]):
    if k[i] == 0:
        su += 1
        
print(su)

Submission status: Accepted

Solution code:
n,m,t=map(int,input().split())
d=0
a=[int(i) for i in input().split()]
b=a[0]-m
c=a[0]+m
for i in range(1,n):
    if a[i]>c+m:
        d+=c-b
        b=a[i]-m
    c=a[i]+m
if c<t:d+=c-b
else:d+=t-b
print(t-d)

Submission status: Accepted

Solution code:
N, M, T = map(int, input().split())
A = [int(x) for x in input().split()]
print(A[0] - M + max(T - A[-1] - M, 0) + sum(max(0, A[i+1] - A[i] - 2 * M) for i in range(N - 1)))

Submission status: Accepted

Solution code:
N, M, T = list(map(int, input().split()))
a = list(map(int, input().split()))
b = [a[0]]
for i in range(1, N):
    b.append(a[i] - a[i-1])
b.append(T-a[N-1])

ans = 0
ans += b[0] - M
for i in range(1, N):
    ans += max(0, b[i]-2*M)
ans += max(0, b[N]-M)
print(ans)

Submission status: Accepted

Solution code:
n, m, t = map(int, input().split())
B = [0]*t
*A, = map(int, input().split())
for a in A:
    B[a-m] += 1
    if a+m < t:
        B[a+m] -= 1
cnt = ans = 0
for b in B:
    cnt += b
    if cnt == 0:
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M,T = map(int,input().split())
src = list(map(int,input().split()))
back_time = ans = 0
for t in src:
    if t - M > back_time:
        ans += (t - M - back_time)
    back_time = t + M
ans += max(0, T - back_time)
print(ans)

Submission status: Accepted

Solution code:
N, M, T = map(int, input().split())
a = list(map(int, input().split()))
current = 0
ans = 0
ans += max(a[0] - M, 0)
current = a[0]
for i in range(1, N):
    ans += max(a[i] - a[i - 1] - 2 * M, 0)
    current = a[i]
ans += max(T - a[N - 1] - M, 0)
print(ans)

Submission status: Accepted

Solution code:
n, m, t = map(int, input().split())
a = list(map(int, input().split()))
s = t
for i in range(n):
    if i == 0:
        s -= m
    elif a[i] - a[i - 1] >= 2 * m:
        s -= 2 * m
    else:
        s -= a[i] - a[i - 1]
    if i == n - 1:
        s -= min(t - a[-1], m)
print(s)

Submission status: Accepted

Solution code:
n, m, t = map(int, input().split())
a = list(map(int, input().split()))
a = [-m] + a + [t + m]

ans = 0
for i in range(len(a) - 1):
    if a[i + 1] - a[i] > m * 2:
        ans += a[i + 1] - a[i] - m * 2

print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n,m,t = LI()
        a = [1] * (t+1)
        l = LI()
        for c in l:
            a[c] = 0
        for c in l:
            for ci in range(c+1,min(c+m,t+1)):
                if a[ci] < 1:
                    break
                a[ci] = 0
            for ci in range(c-1,max(-1,c-m),-1):
                if a[ci] < 1:
                    break
                a[ci] = 0
        r = 0
        for i in range(t):
            if a[i] == 1 and a[i+1] == 1:
                r += 1

        rr.append(r)
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
l_raw = input().split()
l = [int(n) for n in l_raw]
a_raw = input().split()
a_ = [int(n) for n in a_raw]

study = 0
state = 0
now=0

for a in a_:
    if state==0:
        if l[1]<a-now:
            study+=a-now-l[1]
        now=a
        state=1
    elif state==1:
        if 2*l[1]<a-now:
            study+=a-now-2*l[1]
        now=a

if l[2]-l[1]-a>0:
    study+=l[2]-l[1]-a
    
print(study)

Submission status: Accepted

Solution code:
n, m, t = map(int, input().split())
a = list(map(int, input().split()))
ts = [0 for i in range(t)]
for i in a:
    ts[max(i - m, 0)] = 2 * m
temp = 0
count = 0
for i in range(1, t):
    ts[i] = max(ts[i - 1] - 1, ts[i])
print(ts.count(0))

Submission status: Accepted

Solution code:
N, M, T = map(int, input().split())
A = list(map(int, input().split()))
prv = 0
cnt = 0
for a in A:
    if prv == 0:
        cnt += a - M
    else:
        if prv + M < a - M:
            cnt += (a - M) - (prv + M)
    prv = a
if prv + M < T:
    cnt += T - (prv + M)

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

def main():
	n, m, t = map(int, input().split())
	diff_sum = 0
	mini_diff = 0
	a = [-1*m] + [i for i in map(int, input().split())]
	for i in range(n):
		diff = (2 * m) - (a[i+1] - a[i])
		if diff > 0:
			diff_sum += diff
	if t-m < a[n]:
		mini_diff = a[n] + m - t
	print( t - (2*m*n - diff_sum - mini_diff) )
	return

main()

Submission status: Accepted

Solution code:
(n, m, t) = tuple(map(int, input().split()))
arr = list(map(int, input().split()))
backed = 0
res = 0
for e in arr:
    if e - m > backed:
        res += e - m - backed
    backed = e + m
if arr[-1] + m < t:
    res += t - arr[-1] - m
print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

a = list(map(int,input().split()))

b = list(map(int,input().split()))

k = [0]*a[2]
pp = 0
su = 0

for i in b:
    for j in range(a[2]):
        if j >= i - a[1]   and j <= i + a[1] - 1:
                k[j] += 1
            
for i in range(a[2]):
    if k[i] == 0:
        su += 1
        
print(su)

Submission status: Accepted

Solution code:
N,M,T=map(int,input().split())
l=list(map(int,input().split()))
t=0
for (i,j) in enumerate(l):
    if not i:
        t+=(l[i]-M)
    elif (l[i]-l[i-1])>2*M:
        t+=(l[i]-l[i-1])-2*M
if T-l[-1]>M:
    t+=(T-l[-1])-M
print(t)

Submission status: Accepted

Solution code:
#21:25
n,m,t = map(int,input().split())
arrive_time = list(map(int,input().split()))

#
list_time = [0]*(t+m+1)

for i in arrive_time:
    # out of bounsの場合どうしよう
    list_time[i-m] += 1
    list_time[i+m] -= 1

for i in range(1,t):
    list_time[i] += list_time[i-1]

print(sum(x==0 for x in list_time[:t]))

Submission status: Accepted

Solution code:

N, M, T = map(int, input().split())

a = list(int(i) for i in input().split())
count = 0
count += max(a[0] - M,0)
for i in range(1,N):
	count += max(a[i] - a[i-1] -2*M, 0)
count += max(T - a[N-1] - M,0)
print(count)

Submission status: Accepted

Solution code:
n,m,t = map(int,input().split())
a = list(map(int,input().split()))
ans = a[0] - m
for i,aa in enumerate(a):
	if i != 0 and (aa - a[i-1]) >= 2*m:
		ans += (aa - a[i-1] - 2*m )
	if i == len(a)-1 and (t - aa) >= m:
		ans +=  (t - aa - m)
		continue
print(ans)

Submission status: Accepted

Solution code:
"豪邸と宅配便"
N, M, T = map(int, input().split())  # 荷物の個数N, 片道の時間M, 終了時刻T

A = list(map(int, input().split()))

arraival_span = [A[0]]
for i in range(1, N):
    arraival_span.append(A[i] - A[i-1])
# print(arraival_span)

# 最後にT - A[-1]を加える
ans = arraival_span[0] - M
for i in range(1, len(arraival_span)):
    ans += max(arraival_span[i]-2*M, 0)

ans += max(T-A[-1]-M, 0)

print(ans)

Submission status: Accepted

Solution code:
n,m,t=map(int,input().split())
a=list(map(int,input().split()))
a.insert(0,-m)
ans=0
for i in range(n):
    if a[i]+2*m<a[i+1]:
        ans+=a[i+1]-a[i]-2*m
if a[-1]+m<t:ans+=t-a[-1]-m
print(ans)

Submission status: Accepted

Solution code:
n, m, t = map(int, input().split())
a_list = list(map(int, input().split()))
ans = 0
ans += max(0, a_list[0] - m)
before = a_list[0]
for i in range(1, n):
    ans += max(0, a_list[i]-before-m*2)
    before = a_list[i]
ans += max(0, t-before-m)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
n,m,t=map(int,input().split())
a=list(map(int,input().split()))
d=[0]
for time in a:
    f=False
    if d[-1]<time-m:
        d.append(max(time-m,0))
    else:
        f=True
    if f:
        d[-1]=max(d[-1],time+m)
    else:
        d.append(min(time+m,t))
del d[0]
data=[False for i in range(t)]
i=0
while i<len(d)-1:
    data[d[i]:d[i+1]]=[True for j in range(len(data[d[i]:d[i+1]]))]
    i+=2
print(data.count(False))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

a = list(map(int,input().split()))

b = list(map(int,input().split()))

d = 0
k = 0
su = 0

for i in range(a[2]):
    k += 1
    su = max(su,k)
    if b[d] = i + 1:
        k = 0
    
print(su)