시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB195937947.305%

문제

홍익대학교 컴퓨터공학과 승준이는 '알고리즘 분석' 수업을 수강한다.

교수님은 수업에서 실력과 열정을 가장 중요하게 보며, 수업이 진행되는 $N$일 동안 매일 두 값의 곱을 점수에 더한다.

즉, $i$일차의 실력과 열정을 각각 음이 아닌 정수로 수치화한 값을 $A_i$, $B_i$라 하면, 최종 점수는 아래와 같다.

$$A_1B_1+A_2B_2+\cdots+A_NB_N$$

초기 상태에서 승준이의 실력은 $A_0$, 열정은 $B_0$이다.

과도한 공부는 열정의 손실을 일으키고 과도한 열정은 자만을 불러 실력을 줄인다.

승준이는 매일 $i$($i=1,\dots,N$)일차 성적 갱신 전에 두 행동 중 하나를 선택해 현재 상태를 갱신해야 한다.

  1. $x$만큼 공부한다 : 열정 수치에서 $K$이상인 정수 $x$를 선택해 실력으로 바꾼다.
    • $A_{i} = A_{i-1} + x,\ B_{i} = B_{i-1} - x \ (K \le x \le B_{i-1})$
  2. $x$만큼 쉰다 : 실력 수치에서 $K$이상인 정수 $x$를 선택해 열정으로 바꾼다.
    • $A_{i} = A_{i-1} - x,\ B_{i} = B_{i-1} + x \ (K \le x \le A_{i-1})$

매일 $K$이상의 열정을 실력으로 바꾸거나, $K$이상의 실력을 열정으로 바꿔야한다는 뜻이다.

목표는 승준이가 매일 적당한 행동을 선택해 $N$일 후의 최종 점수를 최대로 만드는 것이다.

$N$일차 수업이 종료된 후에 승준이가 얻을 수 있는 최종 점수를 최대화해 보자.

입력

첫번째 줄에 $N$이 주어진다. ($1 \le N \le 500$)

두번째 줄에 승준이의 초기 실력 수치 $A_0$, 초기 열정 수치 $B_0$, 실력과 열정의 변환 가능한 최소 수치인 $K$가 주어진다.

  • $2 \le A_0 + B_0 \le 500$
  • $0 \le A_0, B_0 \le 500$
  • $1 \le K \le \max(A_0, B_0)$

출력

$N$일차 수업이 종료된 후 승준이가 얻을 수 있는 최종 점수의 최댓값을 출력한다.

예제 입력 1

79
1 1 1

예제 출력 1

39

예제 입력 2

3
52 31 11

예제 출력 2

5086

수업이 3일간 진행되고

  • 1일차: 쉬기($x=14$) $A_1=38, B_1=45, A_1B_1=1710$
  • 2일차: 공부($x=11$) $A_2=49, B_2=34, A_2B_2=1666$
  • 3일차: 쉬기($x=11$) $A_3=38, B_3=45, A_3B_3=1710$

위와 같이 행동하면 1일차에 1710, 2일차에 1666, 3일차에 1710의 성적을 얻게 되어 총 5086으로 성적을 최대화 할 수 있다.

출처

University > 홍익대학교 > 2025 HICON 홍익대학교 프로그래밍 경진대회 E번