Submission #123007

#	Time	Username	Problem	Language	Result	Execution time	Memory
123007		model_code	Olympiads (BOI19_olympiads)	Cpython 3	44 / 100	2052 ms	13152 KiB

olympiads

from heapq import heappush, heappop
from collections import namedtuple
from copy import copy

Shard = namedtuple('Shard', ['score', 'best', 'forced', 'forbitten'])

n, k, c = [int(x) for x in input().split(' ')]
scores = [[int(x) for x in input().split(' ')] for i in range(n)]

def pairwise_max(a, b):
    return [max(a[i], b[i]) for i in range(len(a))]

def evaluate_shard(shard):
    best = []
    event_best = [0] * k
    for x in shard.forced:
        best.append(x)
        
    for i in range(len(shard.forced), k):
        best.append(-1)
        for j in range(n):
            if not shard.forbitten[j] and j not in best:
                if best[i] == -1 or scores[j][i] > scores[best[i]][i]:
                    best[i] = j
    
    for c in best:
        event_best = pairwise_max(event_best, scores[c])
    return(Shard(-sum(event_best), best, shard.forced, shard.forbitten))
    

heap = [Shard(0, [], [], [False]*n)]
heap[0] = evaluate_shard(heap[0])
results = []

while len(results) < c:
    top = heappop(heap)
    results.append(-top.score)
    
    new_forced = copy(top.forced)
    new_forbitten = copy(top.forbitten)
    
    
    for i in range(len(top.forced), k):
        new_forbitten[top.best[i]] = True
        new_shard = evaluate_shard(Shard(0, [], copy(new_forced), copy(new_forbitten)))
        if -1 not in new_shard.best:
            heappush(heap, new_shard)
        new_forced.append(top.best[i])

print(results[c-1])
    

• Subtask 1: 13 / 13
• Subtask 2: 31 / 31
• Subtask 3: 0 / 24
• Subtask 4: 0 / 32