ABC 018 D バレンタインデー (python)

女子の選びだけ itertool で nCp 通り全列挙して男子の選び方を貪欲に選んでいく。
collection.Counter で most_common(q) とかして選んでいたら TLE したので普通にリストに入れていって上から q 番目まで取ったらいけた。

import sys
input = sys.stdin.readline
n,m,p,q,r = map(int,input().split())
l = [[] for i in range(n)]
for i in range(r):
  A,B,C = map(int,input().split())
  l[A-1].append((B-1,C))

ans = 0
import itertools
for i in itertools.combinations(range(n),p):
  chk = 0
  cnt = [0]*m
  for a in i:
    for b,c in l[a]:
      cnt[b] += c
  cnt.sort()
  chk = sum(cnt[m-q:])
  ans = max(ans,chk)
  
print(ans)