|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
V Copa UHEnded |
E - Buenos atletas
Languages: C, C++, Java, Tiger, Python, Pascal, JavaScript, Haskell, C#
Time & Memory limits: (details)
En una escuela de atletismo se están formando los grupos para el nuevo curso. El verano anterior todos los nuevos alumnos participaron en un maratón y se conoce para cada uno el lugar en que terminó la carrera.
Se van a formar $n$ grupos y cada uno va a tener $2k$ alumnos. Para hacer la matricula se tendrá en cuenta el resultado en el maratón y las opiniones de los estudiantes. Algunos de estos quieren estar entre los $k$ más rápidos de su aula, para pasar fácilmente las pruebas clasificatorias. Los otros, en cambio, quieren estar entre los $k$ más lentos para tener mayor competencia en las carreras. Teniendo las $2kn$ opiniones y el lugar de cada uno de ellos en el maratón, debemos decidir como formar las matriculas para complacer así a la mayor cantidad de estudiantes.
Se van a formar $n$ grupos y cada uno va a tener $2k$ alumnos. Para hacer la matricula se tendrá en cuenta el resultado en el maratón y las opiniones de los estudiantes. Algunos de estos quieren estar entre los $k$ más rápidos de su aula, para pasar fácilmente las pruebas clasificatorias. Los otros, en cambio, quieren estar entre los $k$ más lentos para tener mayor competencia en las carreras. Teniendo las $2kn$ opiniones y el lugar de cada uno de ellos en el maratón, debemos decidir como formar las matriculas para complacer así a la mayor cantidad de estudiantes.
Input
La primera línea de la entrada contiene dos enteros $k$ y $n$, separados por un espacio, $(2 \leq 2kn \leq 200000)$ que indican respectivamente la mitad de estudiantes en un grupo y la cantidad de grupos a formar. En la segunda línea aparecen $2kn$ enteros, separados por un espacio, representando la posición $P_{i}$ $(1 \leq P_{i} \leq 10^{6} )$ de cada estudiante en la carrera de maratón. Ha de tenerse en cuenta que no todos los participantes de la carrera formarán parte de los grupos y que nunca dos estudiantes terminan en la misma posición. La última línea contiene $2kn$ enteros separados por un espacio, donde $D_{i}$ es cero si el estudiante i-ésimo quiere estar entre los $k$ primeros de su aula y uno en caso contrario.
Output
La salida debe ser un número entero indicando la mayor cantidad de estudiantes que pueden cumplir su deseo.
Sample test(s)
Input
1 2
1 2 3 4
0 1 1 1
Output
3