31814번 - Sequence and Queries 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 180 | 112 | 97 | 69.286% |
문제
길이가 $n$인 수열 $(s_1,s_2,\ldots ,s_n)$이 주어진다. 함수 $f$는 다음과 같이 정의된다.
\[f(i,j,k) =\begin{cases}1&\text{if } s_{i+t}\leq s_{j+t}\text{ for all } 0\leq t<k\\ 0&\text{otherwise}\end{cases}\]
$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{\min(n-i+1,n-j+1)}f(i,j,k)$의 값을 출력하라.
입력
첫 번째 줄에 수열의 길이를 나타내는 정수 $n$이 주어진다.
두 번째 줄에 $n$개의 정수 $s_1,s_2,\ldots ,s_n$이 공백으로 구분되어 주어진다.
출력
$\sum_{i=1}^{n}\sum_{j=1}^{n}\sum_{k=1}^{\min(n-i+1,n-j+1)}f(i,j,k)$의 값을 출력한다.
제한
- $1\leq n\leq 5\, 000$
- $1\le s_x\le 10^9$ ($1\le x\le n$)
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 8 | $1\leq n \leq 500$ |
| 2 | 92 | 추가적인 제약 조건이 없다. |
예제 입력 1
2 2 3
예제 출력 1
4
예제 입력 2
5 2 4 2 2 1
예제 출력 2
35
노트
첫 번째 예제에 대한 설명은 다음과 같다.
- $f(1,1,1) =1$
- $f(1,1,2) =1$
- $f(1,2,1) =1$
- $f(2,1,1) =0$
- $f(2,2,1) =1$
출처
University > KAIST > KAIST RUN Spring Contest > 2024 KAIST RUN Spring Contest B번
- 문제를 만든 사람: knon0501
- 문제를 검수한 사람: 79brue, abra_stone, ai4youej, flakepowders, flappybird, koosaga, octane, parkky, qwerasdfzxcl
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호