No.3049 Contest Coordinator
タグ : / 解いたユーザー数 84
作問者 :
suisen
/ テスター :
ochiaigawa
👑 
rin204
Story
When holding a contest, we want to create a problem set with as few difficulty inversions and difficulty cliffs as possible.
Problem Statement
You are given a sequence of positive integers $D = (D _ 1, D _ 2, \ldots, D _ N)$ of length $N$, a non-negative integer $T$, and positive integers $X, Y$.
For $T,X,Y$, the dissatisfaction $f(A)$ of a sequence $A = (A _ 1, A _ 2, \ldots, A _ k)$ of length $k$ is defined as follows.
Definition of $f(A)$
Let $p$ be the number of integers $i\in\lbrace 1,2,\ldots,k-1\rbrace$ satisfying $A _ {i + 1} - A _ i \gt T$, and let $q$ be the number of those satisfying $A _ {i + 1} - A _ i \lt 0$. Then $f(A) \coloneqq pX + qY$.
Solve the following (Problem $k$) for all $k = 1,2,\ldots, N$.
(Problem $k$)
Find the minimum dissatisfaction among sequences of length $k$ that can be formed by taking $k$ elements from $D$ and arranging them in any order.
More formally, find $\displaystyle \min _ {I \in \mathcal{I} _ {N, k}} f(D\lbrack I\rbrack)$. Here, $\mathcal{I} _ {N, k}$ is the set of all integer sequences $I = (I _ 1, I _ 2, \ldots, I _ k)$ of length $k$ satisfying all of the following conditions, and $D\lbrack I\rbrack \coloneqq (D _ {I _ 1}, D _ {I _ 2}, \ldots, D _ {I _ k})$.
- For every $i \in \lbrace 1,2,\ldots,k\rbrace$, $I _ i\in\lbrace 1,2,\ldots,N\rbrace$.
- For every $i, j\in \lbrace 1,2,\ldots,k\rbrace$, if $i \neq j$ then $I _ i \neq I _ j$.
Input
The input is given from standard input in the following format.
$N$ $T$ $X$ $Y$ $D _ 1\ D _ 2 \ \cdots \ D _ N$
- All input values are integers.
- $1\leq N\leq 5\times 10 ^ 5$
- $0\leq T\leq 10 ^ 9$
- $1\leq X,Y \leq 10 ^ 9$
- $1\leq D _ i \leq 10 ^ 9$
Output
Let $S _ k$ be the answer to (Problem $k$). Print $S _ 1, S _ 2, \ldots, S _ n$ in this order, separated by spaces, followed by a newline.
$S _ 1\ S _ 2 \ \cdots \ S _ n$
Sample
Sample 1
Input
3 2 1 2 1 7 5
Output
0 0 1
This input represents $N = 3,\ T = 2,\ X = 1,\ Y = 2,\ D = (1,7,5)$.
- For $k = 1$, the possible sequences are the $3$ sequences $(1),\ (7),\ (5)$, all of which have dissatisfaction $0$. Therefore, the answer for $k=1$ is $0$.
- For $k = 2$, the possible sequences are the $6$ sequences $(1,7),\ (7,1),\ (1,5),\ (5,1),\ (7,5),\ (5,7)$. Their dissatisfaction values are as follows, so the answer for $k=2$ is $0$.
- $(1,7),\ (1,5)$ have $p=1,\ q=0$, so their dissatisfaction is $1$.
- $(7,1),\ (5,1),\ (7,5)$ have $p=0,\ q=1$, so their dissatisfaction is $2$.
- $(5,7)$ has $p=0,\ q=0$, so its dissatisfaction is $0$.
- For $k = 3$, the possible sequences are the $6$ sequences $(1,7,5),\ (7,1,5),\ (1,5,7),\ (5,1,7),\ (7,5,1),\ (5,7,1)$. Their dissatisfaction values are as follows, so the answer for $k=3$ is $1$.
- $(1,7,5),\ (7,1,5),\ (5,1,7)$ have $p=1,\ q=1$, so their dissatisfaction is $3$.
- $(1,5,7)$ has $p=1,\ q=0$, so its dissatisfaction is $1$.
- $(5,7,1)$ has $p=0,\ q=1$, so its dissatisfaction is $2$.
- $(7,5,1)$ has $p=0,\ q=2$, so its dissatisfaction is $4$.
Sample 2
Input
5 4 3 2 1 1 1 1 1
Output
0 0 0 0 0
The dissatisfaction is always $0$ no matter how the elements are chosen.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。