[Medium] SRMIntermissionPhase
Topcoder SRM 520 Div1
간단한 DP로 해결할 수 있다.
C_i[j][k] = 스코어보드에서 i등인 사람이 1번~j번 문제까지 얻은 점수의 합이 k일 경우의 수
= sum( C_i[j-1][k-x] , (j번 문제의 minScore) <= x <= (j번 문제의 maxScore) )
D[i][j] = 스코어보드에서 i등~N등을 배정했고, i등인 사람의 총점이 j점 이하인 경우의 수
= D[i][j-1] + D[i+1][j-1] * C_i[3][j]
C_i 를 구할 때, 누적합을 이용하면 시간내에 구할 수 있다.
답은 D[1][200000]