ABC127
atcoder.jp
土曜にあったやつです。
30分遅れで初めて、A-Cの3完。
Dは時間内では、カードをソートして入れ替えて、をM回やるTLE待ったなしな方法しか思いつかなくてダメでした。
後に上書きされるような小さい数のBを入れ替えるという操作は、無駄になるわけですね。
その後Aを小さい順ソート、BjをCj回並べた(j=[1, M])配列BCを大きい順にソートしてAとBCをの要素を大きい方で入れ替える、
という方法を思いついたけど、これもTLE。
うーん。。と思ったけどこれはBCが大きくなりすぎて起こってたもので、BCの要素数をNまでにしとけばOKでした。
N, M = map(int, input().split()) A = list(map(int, input().split())) count = 0 BC = [] for i in range(M): b, c = map(int, input().split()) BC.append((b, c)) A.sort() BC.sort(reverse=True, key=lambda x: x[1]) count = 0 CArr = [] for b, c in BC: if count >= N: break for i in range(b): CArr.append(c) count += 1 if count >= N: break for i in range(len(CArr)): if A[i] < CArr[i]: A[i] = CArr[i] ans = sum(A) print(ans)
E、Fは難しそうだったのでスルー。。ひとまず4完目指したい