Submission #676020

#	Time	Username	Problem	Language	Result	Execution time	Memory
676020		frferreira	Martian DNA (BOI18_dna)	Cpython 3	100 / 100	484 ms	28960 KiB

dna

def validacao(v, w, n,k,r):
    t = [0] * k
    for x in v:
        t[x] += 1
    for i in range(k):
        if w[i] > t[i]: 
            return False
        #if w[i] > n: 
        #    return False
    
    return True                                    



n,k,r = map(int, input().split())
v = list(map(int, input().split()))

#if r < 1 or k < 1 or n<1: 
#    print("impossible")
#    exit(0)    
#
#if k > n: 
#    print("impossible")
#    exit(0)    
#
#if r > k: 
#    exit(0)    
#    print("impossible")


failed = 0
have = [0] * k
wanted = [0] * k
for i in range(r):
    sym, co = map(int, input().split())
    wanted[sym] = co
    failed += 1

#print(f"falha: {failed}")

if not validacao(v, wanted, n,k,r): 
    print("impossible")
    exit(0)    
j = 0
d = 0
i = 0
res = 999999999999999
while True:
    if failed > 0:
        if j == n:
            break
        have[v[j]] += 1
        if have[v[j]] == wanted[v[j]]:
            failed -= 1
        j += 1
    else:
        dif = j - i
        if dif < res:
            res = dif
        if have[v[i]] == wanted[v[i]]:
            failed += 1
        have[v[i]] -= 1
        i += 1
        #if i > n:
        #    break
if res == 999999999999999:
    print("impossible")
    exit(0)    

print(res)        

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32