Submission #47871

#	Time	Username	Problem	Language	Result	Execution time	Memory
47871		leejseo	격자 보존하기 (GA9_preserve)	Cpython 2	100 / 100	192 ms	26320 KiB

preserve

range = xrange
n, k, d = map(int, raw_input().split())
p = map(int, raw_input().split())
inter = [0]*(k+1)
for i in range(1, k):
    inter[i] = p[i] - p[i-1] - 1
inter[0] = p[0] - 1
inter[-1] = n - p[-1]
if d == 1 :
    print max(inter[0], inter[-1])
elif d == 2 :
    print max(max(inter), inter[0] + inter[-1])
elif d % 2 == 0:
    inter[0] += inter.pop()
    inter.sort()
    inter.reverse()
    ans = 0
    for i in range(min(d/2, len(inter))):
        ans += inter[i]
    print ans
else:
    ans1, ans2 = 0, 0
    ans1 = max(inter[0], inter[-1])
    inter1 = inter[1:len(inter)-1]
    inter1.sort()
    inter1.reverse()
    for i in range(min(d/2, len(inter1))):
        ans1 += inter1[i]
    inter[0] += inter.pop()
    inter.sort()
    inter.reverse()
    for i in range(min(d/2, len(inter))):
        ans2 += inter[i]
    print max(ans1, ans2)

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 22 / 22
• Subtask 4: 17 / 17
• Subtask 5: 35 / 35