日刊競プロ ABC 228 -C - Final Day-
問題文
N 人の生徒が 4 日間にわたる試験を受けています。
それぞれの日に行われる試験は 300 点満点です。すなわち、4 日間を通した試験の満点は 1200 点です。
現在 3 日目までの試験が終わり、これから 4 日目の試験が行われようとしています。i(1≤i≤N) 番目の生徒は j(1≤j≤3) 日目の試験で Pi,j点獲得しました。
それぞれの生徒について、4 日目の試験後に上位 K 位以内に入っていることがあり得るかどうか判定してください。
ただし、4 日目の試験後の生徒の順位は、その生徒よりも 4 日間の合計点が高い生徒の人数に 1 を加えた値として定めます。
制約
1≤K≤N≤10**5
0≤Pi,j≤300(1≤i≤N,1≤j≤3)
入力は全て整数である。
考えたこと
最後に300点がプラスされる可能性があることを吟味し，最終的な順位がK位以内になれば良いことを考える．K位以内になるのでそれぞれの人の点数の和を計算しておき，リスト化，ソートし昇順にする．（sumlistとする）．K位以内になるためには昇順にした際に,sumlist[-K]番目の数より大きくなれば良い．最後に300点を加えてそれを上回ることができればYes,そうでなければNo．
N,K = map(int,input().split())
plist =[]
for i in range(N):
p1,p2,p3 = map(int,input().split())
plist.append(p1+p2+p3)
p2list = sorted(plist)
tempmax =p2list[-K]
for i in range(N):
if plist[i]+300>=tempmax:
print ("Yes")
else:
print ("No")減点方式があればDPで解くことになるのかなぁ・・・？