USACO Why Did The Cow Cross The Road II

USACO 2017 FEBRUARY CONTEST, SILVER¶

PROBLEM 2. WHY DID THE COW CROSS THE ROAD II¶

http://www.usaco.org/index.php?page=viewproblem2&cpid=721

In [1]:

fin = open("maxcross.in", "r")
fout = open("maxcross.out", "w")
N,K,B = map(int,fin.readline().split())
print(N,K,B)

10 6 5

In [2]:

crossings = [1]*N
for i in range(B):
    b = int(fin.readline().strip())
    crossings[b-1]=0
    
print(crossings)

[0, 0, 1, 1, 0, 1, 1, 1, 0, 0]

In [3]:

prefixsum = [0]*N
prefixsum[0] = crossings[0]
maxworking = 0

for i in range(1,K):
    prefixsum[i] = prefixsum[i-1]+crossings[i]
    
maxworking = prefixsum[K-1]

for i in range(K,N):
    prefixsum[i] = prefixsum[i-1]+crossings[i]
    maxworking = max(maxworking,prefixsum[i]-prefixsum[i-K])
    if maxworking==6:
        break

print(prefixsum)
print("maxworking",maxworking)

[0, 0, 1, 2, 2, 3, 4, 5, 5, 5]
maxworking 5

In [4]:

ans = K-maxworking
print("answer",ans)
fout.write(str(ans)+"\n")
fout.close()

answer 1