oj.uz

Submission #123007

# Submission time Handle Problem Language Result Execution time Memory
123007 2019-06-30T01:38:15 Z model_code Olympiads (BOI19_olympiads) Python 3
44 / 100
 2000 ms 13152 KB 
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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 4316 KB Output is correct
2 Correct 522 ms 4420 KB Output is correct
3 Correct 468 ms 4188 KB Output is correct
4 Correct 379 ms 4220 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 4924 KB Output is correct
2 Correct 147 ms 4196 KB Output is correct
3 Correct 309 ms 5988 KB Output is correct
4 Correct 268 ms 5304 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 612 ms 4320 KB Output is correct
2 Correct 462 ms 4192 KB Output is correct
3 Execution timed out 2052 ms 13152 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 452 ms 4316 KB Output is correct
2 Correct 522 ms 4420 KB Output is correct
3 Correct 468 ms 4188 KB Output is correct
4 Correct 379 ms 4220 KB Output is correct
5 Correct 215 ms 4924 KB Output is correct
6 Correct 147 ms 4196 KB Output is correct
7 Correct 309 ms 5988 KB Output is correct
8 Correct 268 ms 5304 KB Output is correct
9 Correct 612 ms 4320 KB Output is correct
10 Correct 462 ms 4192 KB Output is correct
11 Execution timed out 2052 ms 13152 KB Time limit exceeded
12 Halted 0 ms 0 KB -