Python list sort and simulation optimization problem

Question

I am once again trying to solve a problem to practice for the upcoming USACO contest, and am having trouble meeting the time limit of 1 second: https://open.kattis.com/contests/v4xrif/problems/knigsoftheforest

All moose are knigs of the forest, but your latest moose-friend, Karl-Älgtav, is more interesting than most. In part because of his fondness of fermented blueberries, and in part because of the tribe he lives in. Each year his tribe holds a tournament to determine that year’s alpha-moose. The winner gets to lead the tribe for a year, and then permanently leaves the tribe. The pool of contenders stays constant over the years, apart from the old alpha-moose being replaced by a newcomer in each tournament.

Karl-Älgtav has recently begun to wonder when it will be his turn to win, and has asked you to help him determine this. He has supplied a list of the strength of each of the other moose in his tribe that will compete during the next n−1 years, along with their time of entry into the tournament. Assuming that the winner each year is the moose with greatest strength, determine when Karl-Älgtav becomes the alpha-moose.

Input The first line of input contains two space separated integers k (1≤k≤100000) and n (1≤n≤100000), denoting the size of the tournament pool and the number of years for which you have been supplied sufficient information.

Next is a single line describing Karl-Älgtav, containing the two integers y (2011≤y≤2011+n−1) and p (0≤p≤2^31−1). These are his year of entry into the tournament and his strength, respectively.

Then follow n+k−2 lines describing each of the other moose, in the same format as for Karl-Älgtav.

Note that exactly k of the moose will have 2011 as their year of entry, and that the remaining n−1 moose will have unique years of entry.

You may assume that the strength of each moose is unique.

Output The year Karl-Älgtav wins the tournament, or unknown if the given data is insufficient for determining this.

Sample Input 1

2 4
2013 2
2011 1
2011 3
2014 4
2012 6

Sample Output 1

2013

Sample Input 2

2 4
2011 1
2013 2
2012 4
2011 5
2014 3

Sample Output 2

unknown

My logic: Get all the moose, and sort them by strength. Then just simulate by year from there, removing the winners of each year from the list of all moose, and breaking out of the loop if Karl-Älgtav is the winner. if the loop is completed and we haven't broken out, we do not know when he will win so we print 'unknown'

My code:

line = input().strip().split()
k, n = int(line[0]), int(line[1])
line = input().strip().split()
m = (int(line[0]), int(line[1]))
c = [None for i in range(n+k-1)]
for i in range(n+k-2):
    line = input().strip().split()
    c[i] = ((int(line[0]), int(line[1])))
c[-1] = m
c.sort(key = lambda i:i[1])

year = 2011
won = False
for i in range(n):
    yc = [y for y in c if y[0] <= year]
    w = yc[-1]
    c.remove(w)
    if w == m:
        print(year)
        won = True
        break
    year += 1
    
if not won:
    print('unknown')

I am trying to speed this up but failing. Can anybody else figure it out? I've also noticed recently that for most competitive programming problems, if you can't brute force it in Python, you can in Java or C++. For competitive programming, is it recommended that I spend more time learning those languages or learning to better optimize in Python?

I tried a different approach with a dictionary and a heap, but it still didn't reach the time limit. It got one test case further though

Code:

from heapq import heappop, heappush, heapify

line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = {karl[1] : karl[0]}
for i in range(N+K-2):
    line = input().strip().split()
    moosen[int(line[1])] = (int(line[0]))

heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
    mc = moosen.copy()
    for k,v in moosen.items():
        if v <= year:
            heappush(heap, -k)
            mc.pop(k)
    moosen = mc.copy()

    if -heappop(heap) == karl[1]:
        won = True
        print(year)
        break

if not won:
    print('unknown')

Answer 1

So basically I modified my second approach (see question) so that the keys and values reversed, which made the dictionary search much faster! Code:

from heapq import heappop, heappush, heapify
from collections import defaultdict

line = input().strip().split()
K, N = int(line[0]), int(line[1])
line = input().strip().split()
karl = (int(line[0]), int(line[1]))
moosen = defaultdict(list)
for i in range(N+K-2):
    line = input().strip().split()
    moosen[int(line[0])].append(int(line[1]))
moosen[karl[0]].append(karl[1])
heap = []
heapify(heap)
won = False
for year in range(2011, 2011 + N):
    for i in moosen[year]:
        heappush(heap, -i)
    if -heappop(heap) == karl[1]:
        won = True
        print(year)
        break

if not won:
    print('unknown')