Il y a $N$ voitures, numérotées de $0$ à $N-1$, sur une droite numérique. On vous donne les listes de leurs positions $X[0], X[1], \ldots, X[N - 1]$ et de leurs taux de consommation de carburant par unité $C[0], C[1], \ldots, C[N - 1]$, chacune triée par ordre croissant. Cependant, vous ne savez pas quelle voiture correspond à quelle position ou à quel taux de consommation. Mais vous savez que chaque voiture a exactement une position et exactement un taux de consommation.

De manière équivalente, il existe deux permutations $P$ et $Q$ de longueur $N$ telles que la $i$-ième voiture est située à la position $X[P[i]]$ et a un taux de consommation $C[Q[i]]$.

Qu'est-ce qu'une permutation de longueur $N$ ? Dans ce problème, une permutation $P$ de longueur $N$ est un tableau de longueur $N$ tel que $0 \leq P[i] \leq N-1$ pour tout $0 \leq i \leq N-1$ et $P[i] \neq P[j]$ pour tout $0 \leq i < j \leq N-1$. Par exemple, $[2,1,0]$ est une permutation de longueur $3$, mais $[1,2,3]$ et $[2,0,2]$ ne sont pas des permutations de longueur $3$.

Étant donné une affectation particulière $(P, Q)$, nous définissons le coût total en carburant pour rassembler toutes les voitures en un point $y$ comme $\text{cost}(P, Q, y) = \sum_{i=0}^{N-1} \lvert X[P[i]] -y \rvert \times C[Q[i]]$.

Étant donné un point entier $p$, définissons le coût en carburant dans le pire des cas au point $p$ comme le coût total maximal en carburant sur toutes les affectations possibles $(P, Q)$. C'est-à-dire, définissons $\text{worst}(p) = \max\limits_{P,Q} \text{cost}(P, Q, p)$.

Votre tâche est de déterminer un point entier $p$ tel que le coût dans le pire des cas au point $p$, $\text{worst}(p)$, soit minimisé. S'il existe plusieurs points $p$ qui atteignent la même valeur minimale de $\text{worst}(p)$, vous pouvez en rapporter n'importe lequel.

Détails d'implémentation

Vous devez implémenter la procédure suivante :

int car_gathering(int N, std::vector<int> X, std::vector<int> C)

• $N$ : le nombre de voitures.
• $X$ : un tableau de longueur $N$ décrivant les positions des voitures triées par ordre croissant.
• $C$ : un tableau de longueur $N$ décrivant les taux de consommation des voitures triés par ordre croissant.
• Cette procédure est appelée exactement une fois pour chaque cas de test.
• Cette procédure doit retourner un entier $p$, pour lequel le coût en carburant dans le pire des cas pour rassembler toutes les voitures en $p$ est minimisé parmi tous les points entiers.

Contraintes

• $1 \le N \le 10\;000\;000$.
• $-10^9 \le X[i] \le 10^9$, pour tout $0 \leq i \leq N - 1$.
• $\color{red}{0 \le C[i] \le 100}$, pour tout $0 \leq i \leq N - 1$.
• $X[i] \leq X[j]$, pour tout $0 \leq i < j \leq N - 1$.
• $C[i] \leq C[j]$, pour tout $0 \leq i < j \leq N - 1$.

Sous-tâches

1. (10 points) $N \le 1000, \lvert X[i] \rvert \le 10^3$.
2. (23 points) $N \le 100\;000$.
3. (17 points) $N \le 1\;000\;000$.
4. (31 points) $C[i] \le 1$, pour tout $0 \leq i \leq N - 1$.
5. (19 points) Aucune contrainte supplémentaire.

Exemples

Considérez l'appel suivant :

car_gathering(3, [-1, 2, 3], [1, 1, 2])

Supposons $p = 1$. Alors on peut prouver que les affectations $P = [0,1,2]$ et $Q = [2,1,0]$ donnent le coût en carburant dans le pire des cas. C'est-à-dire, $\text{worst}(p) = \text{cost}(P, Q, p) = (\lvert -1 - 1 \rvert \times 2) + (\lvert 2-1 \rvert \times 1) + (\lvert 3-1 \rvert \times 1) = 7$. Notez qu'il pourrait y avoir d'autres affectations de $P$ et $Q$ qui donnent le coût dans le pire des cas, telles que $P = [2,1,0]$ et $Q = [2,1,0]$.

On peut également prouver que le point entier $p = 1$ est le point avec le minimum possible de $\text{worst}(p)$. Par conséquent, cet appel doit retourner 1.

Grader d'exemple

Format d'entrée :

N
X[0] X[1] ... X[N - 1]
C[0] C[1] ... C[N - 1]

Format de sortie :

Un entier représentant la valeur de retour de car_gathering.