| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 189 | 58 | 50 | 42.735% |
무대소녀 바나나는 고등학교 3학년이 되었다. 명문 대학을 가고 싶은 그녀이지만, 평소 연기 연습만을 하며 내신 공부를 전혀 하지 않았던 바나나는 정신을 차리고 $T$시간 뒤에 있는 수능을 위해 공부하기로 마음먹었다. 그러나 공부 경험이 없는 바나나는 공부를 얼마나 해야 하는지를 알 수 없었다. 바나나를 위해 공부 스케줄을 짜주자!
수능에는 $N$개의 과목이 있다. $i$ $(1\leq i\leq N)$번 과목을 총 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수를 $S_{i,j}$ 라 하자. 바나나가 지켜오던 스케줄에 따라, 각 과목의 공부 시간은 음이 아닌 정수여야 함에 주의하자.
그러나 인간의 체력에 한계가 있기 때문에 하루 종일 공부를 하는 것은 힘들다. 총 $X$ $(0\leq X\leq T)$시간 만큼 공부를 하면 피곤해져서 총 점수가 $D_{X}$만큼 감소하게 된다. 이로 인하여 점수가 음수가 될 수도 있음에 주의하자.
당신은 최적의 방법으로 공부를 하였을 때 바나나가 얻을 수 있는 최대 점수와 그때의 공부 방법을 구해야 한다.
첫째 줄에는 수능 과목의 수 $N$과 $T$가 공백으로 구분되어 주어진다.
둘째 줄부터 $N+1$번째 줄까지는 $i+1$ $(1\leq i\leq N)$번째 줄에 $i$번째 과목을 $j$ $(0\leq j\leq T)$시간 공부했을 때 받을 수 있는 점수에 대한 $T+1$개의 수 $S_{i,0},ドル $S_{i,1},ドル $\cdots,ドル $S_{i,T}$가 공백으로 구분되어 주어진다.
$N+2$번째 줄에는 $T+1$개의 수 $D_{0},ドル $D_{1},ドル $\cdots,ドル $D_{T}$가 공백으로 구분되어 주어진다.
입력으로 주어지는 모든 수는 정수이다.
첫째 줄에 바나나가 받을 수 있는 최대 점수 $score$를 출력하라.
둘째 줄에 각 과목 별로 공부해야 하는 시간을 뜻하는 $N$개의 정수 $A_{1},ドル $A_{2},ドル $\cdots,ドル $A_{N}$을 공백으로 구분하여 출력하라. 만약 최대 점수를 받는 공부 방법이 여러 가지라면, 그 중 아무거나 출력해도 좋다.
3 4 0 4 7 9 10 0 5 9 11 12 0 1 2 4 10 0 3 6 9 12
4 1 2 0
School > 선린인터넷고등학교 > 선린 프로그래밍 챌린지 > 제 1회 선린 프로그래밍 챌린지 > Open Contest I번