17677번 - 케이크 3 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 256 MB | 161 | 73 | 54 | 40.299% |
문제
오늘은 IOI양의 생일이다. 이 날을 위해 JOI군은 생일 케이크를 예약했다. 원형 케이크 하나를 통채로 예약할 생각이었지만 착오가 있어서 $N$조각의 케이크를 예약해 버렸다. 각 조각에는 1번 부터 $N$번까지 번호가 붙어 있고, $i$ 번째 ($1 \le i \le N$) 조각의 가치는 $V_i$이고, 색의 짙음은 $C_i$이다.
JOI군은 서로 다른 $M$개의 케이크를 골라, 원하는 순서대로 배열해 합쳐서 원형 케이크를 만들기로 결심했다. 케이크 조각들이 $k_1$번, $\cdots$, $k_M$번 조각의 순서로 나열되어 있을 때, 이 케이크의 아름다움은
$$ \sum_{j=1}^{M} {V_{k_j}} - \sum_{j=1}^{M} {\left| C_{k_j} - C_{k_{j+1}}\right|} $$
으로 정의된다. (단, $k_{M+1} = k_1$ 이다.) 즉, 아름다움은 사용된 케이크 조각의 가치의 합으로 부터 인접한 두 케이크의 색의 짙음에 차의 절댓값의 합계로 정의된다. JOI군은 되도록이면 원형 케이크의 가치의 합을 최대로 하고싶다.
케이크 조각의 갯수, 각 케이크 조각의 가치와 색의 짙음, 원형 케이크를 만들기 위해 필요한 조각의 갯수가 주어졌을 때, JOI군이 만들 수 있는 원형 케이크의 아름다움의 최댓값을 구하는 프로그램을 작성하여라.
입력
표준 입력에서 다음과 같은 형식으로 주어진다. 모든 값은 정수이다.
$N$ $M$
$V_1$ $C_1$
$\vdots$
$V_N$ $C_N$
출력
표준 출력으로 한 개의 줄에 하나의 수를 출력하여라. 이는 JOI군이 만들 수 있는 원형 케이크의 아름다움의 최댓값이다.
제한
- $3 \le N \le 200\ 000$.
- $3 \le M \le N$.
- $1 \le V_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).
- $1 \le C_i \le 1\ 000\ 000\ 000$ ($1 \le i \le N$).
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 5 | N ≤ 100. |
| 2 | 19 | N ≤ 2000. |
| 3 | 76 | No additional constraints. |
예제 입력 1
5 3 2 1 4 2 6 4 8 8 10 16
예제 출력 1
6
JOI군이 조각 1번, 3번, 2번 조각을 골라서 순서대로 붙이면, 조각의 가치의 합은 $2+6+4=12$ 이고, 케이크의 짙음의 차이 합은 $|1-4|+|4-2|+|2-1|=6$이다. 그래서 원형 케이크의 아름다움은 $12-6=6$이다.
또한, 2번, 3번, 4번 조각을 골라서 순서대로 붙여서 아름다움이 6인 원형 케이크를 만들 수도 있다.
더 아름다운 원형 케이크를 만들 수는 없기 때문에, 6을 출력해야 한다.
예제 입력 2
8 4 112103441 501365808 659752417 137957977 86280801 257419447 902409188 565237611 965602301 689654312 104535476 646977261 945132881 114821749 198700181 915994879
예제 출력 2
2323231661
출처
Camp > JOI Spring Training Camp > JOI 2018/2019 Spring Training Camp 4-1번
- 문제를 번역한 사람: ho94949
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호