시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 256 MB | 536 | 72 | 35 | 15.021% |
이번 학기 지스트에는 총 $m$개의 과목이 개설되며, 청응이는 이번 학기에 $n_\text{lo}$학점 이상, $n_\text{hi}$학점 이하를 듣고자 한다. 청응이는 개설 교과목 목록을 보며 모든 강의에 대해 행복도를 매겼고, 이번 학기의 행복도는 수강하는 모든 과목의 행복도의 합으로 정의한다. 시간표는 고려할 필요가 없다. 청응이가 이번 학기 가질 수 있는 최대 행복도를 구하는 프로그램을 작성하시오.
첫 줄에는 최소와 최대 수강 학점 $n_\text{lo}$, $n_\text{hi}$이 공백으로 구분되어 주어진다. 학점은 $0\leq n_\text{lo}\leq n_\text{hi}\leq 200,000$을 만족한다. 둘째 줄에는 이번학기 개설 교과목의 수 $m$이 주어진다. $1\leq m\leq 200,000$을 만족한다. 셋째 줄부터 $(m+2)$번째 줄까지 각 줄마다 개설 과목에 대한 정보가 다음과 같이 주어진다. $(i+2)$번째 줄에 과목 $i$의 학점 $g_i$와 행복도 $s_i$가 공백으로 구분되어 주어지며, 학점은 $0\leq g_i\leq 5$, 행복도는 $-100\leq s_i\leq 100$를 만족한다. 학점 요건을 충족하는 과목들의 조합이 존재하는 경우만 주어진다.
이번 학기 얻을 수 있는 최대 행복도를 출력한다.
모든 과목의 학점이 $0$학점 혹은 $1$학점인 경우만 주어진다. 즉, 모든 $i$에 대해 $g_i=0$ 혹은 $g_i=1$이다.
최소와 최대 수강 학점 $n_\text{lo}$, $n_\text{hi}$이 $0\leq n_\text{lo}\leq n_\text{hi}\leq 2,000$을 만족하는 경우만 주어진다.
추가 제한 조건이 없다.
2 2 4 0 2 1 1 1 3 1 -1
6
3 5 8 0 2 1 2 2 -2 0 -8 1 0 3 -5 1 -3 0 -1
2
University > 광주과학기술원 > 광주과학기술원 HOLICS 알고리즘 대회 2018 A번