| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 3 초 | 2048 MB | 51 | 13 | 11 | 23.913% |
あるボリビア料理レストランでは 1 から N までの番号が付けられている N 人のシェフが働いている.シェフ i (1 ≦ i ≦ N) は美味しさが Ai であるシルパンチョと美味しさが Bi であるピケマチョを作ることができる.
ただし,シェフはこだわりが強いため仲が悪い 2 人組が M 組いる.仲が悪い 2 人組の j 番目 (1 ≦ j ≦ M) はシェフ Uj とシェフ Vj の 2 人組である.
このレストランに来店する客は以下のようにして料理を食べる.
このレストランに 1 から Q までの番号が付けられている Q 人の客が来店した.
客 k (1 ≦ k ≦ Q) は,料理を作ることを依頼することができる 2 人組のうち,満足度が Xk 番目に高くなる 2 人組に料理を作ることを依頼した.具体的には満足度を S として,S × N2 + p × N + q が Xk 番目に高くなるシェフ p とシェフ q (1 ≦ p < q ≦ N) の 2 人組に料理を作ることを依頼した.
レストランのシェフと客の情報が与えられたとき,客 k (1 ≦ k ≦ Q) の満足度を求めるプログラムを作成せよ.
入力は以下の形式で与えられる.
N M Q A1 A2 … AN B1 B2 … BN U1 V1 U2 V2 : UM VM X1 X2 … XQ
Q 行に出力せよ.k 行目 (1 ≦ k ≦ Q) には客 k の満足度を出力せよ.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | N ≦ 50,M ≦ 50,Q ≦ 50,Xk ≦ 50 (1 ≦ k ≦ Q). |
| 2 | 9 | Bi = 1 (1 ≦ i ≦ N),M = 0,Q = 1. |
| 3 | 10 | Bi = 1 (1 ≦ i ≦ N),Q = 1. |
| 4 | 5 | Bi = 1 (1 ≦ i ≦ N). |
| 5 | 29 | N ≦ 100 000,M ≦ 100 000,Q = 1,X1 = 1. |
| 6 | 14 | N ≦ 100 000,M ≦ 100 000,Q = 1,X1 ≦ 100 000. |
| 7 | 18 | N ≦ 100 000,M ≦ 100 000,Q ≦ 100 000,Xk ≦ 100 000 (1 ≦ k ≦ Q). |
| 8 | 11 | 追加の制約はない. |
4 2 4 2 7 3 5 4 3 4 8 1 3 2 4 1 2 3 4
13 13 11 11
料理を作ることを依頼することができるシェフの 2 人組は 4 通りあり,それぞれにおける客の満足度は以下のようになる.
したがって,それぞれの客について以下のことが分かる.
この入力例は小課題 1,7,8 の制約を満たす.
4 3 1 3 6 5 4 1 1 1 1 1 2 2 3 2 4 1
6
料理を作ることを依頼することができるシェフの 2 人組は 3 通りあり,それぞれにおける客の満足度は以下のようになる.
したがって,客 1 について以下のことが分かる.
この入力例は小課題 1,3,4,5,6,7,8 の制約を満たす.
5 0 4 1 2 3 4 5 5 4 3 2 1 3 9 10 1
9 7 7 10
この入力例は小課題 1,7,8 の制約を満たす.
13 12 10 2 28 28 60 48 77 63 92 13 71 36 91 87 85 7 64 15 55 92 66 91 83 35 49 22 61 2 9 8 13 7 11 9 11 8 12 5 12 4 7 11 12 10 12 4 11 1 5 3 8 49 21 46 13 20 41 6 33 24 7
121 169 129 174 169 137 183 148 169 183
この入力例は小課題 1,7,8 の制約を満たす.
Olympiad > Japanese Olympiad in Informatics > Japanese Olympiad in Informatics Qualification Round > JOI 2024/2025 예선 2 4번