시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 16 | 6 | 5 | 35.714% |
There are a total of $N$ ($1\le N\le 5000$) cows on the number line, each of which is a Holstein or a Guernsey. The breed of the $i$-th cow is given by $b_i\in \{H,G\}$, the location of the $i$-th cow is given by $x_i$ ($0 \leq x_i \leq 10^9$), and the weight of the $i$-th cow is given by $y_i$ ($1 \leq y_i \leq 10^5$).
At Farmer John's signal, some of the cows will form pairs such that
It's up to you to determine the range of possible sums of weights of the unpaired cows. Specifically,
The first input line contains $T$, $N$, and $K$.
Following this are $N$ lines, the $i$-th of which contains $b_i,x_i,y_i$. It is guaranteed that $0\le x_1< x_2< \cdots< x_N\le 10^9$.
The minimum or maximum possible sum of weights of the unpaired cows.
2 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9
16
Cows $2$ and $3$ can pair up because they are at distance $1$, which is at most $K = 4$. This pairing is maximal, because cow $1$, the only remaining Guernsey, is at distance $5$ from cow $4$ and distance $7$ from cow $5$, which are more than $K = 4$. The sum of weights of unpaired cows is $1 + 6 + 9 = 16$.
1 5 4 G 1 1 H 3 4 G 4 2 H 6 6 H 8 9
6
Cows $1$ and $2$ can pair up because they are at distance $2 \leq K = 4$, and cows $3$ and $5$ can pair up because they are at distance $4 \leq K = 4$. This pairing is maximal because only cow $4$ remains. The sum of weights of unpaired cows is the weight of the only unpaired cow, which is simply $6$.
2 10 76 H 1 18 H 18 465 H 25 278 H 30 291 H 36 202 G 45 96 G 60 375 G 93 941 G 96 870 G 98 540
1893
The answer to this example is $18+465+870+540=1893$.