David Compra Paninis

Enviar solució
Punts: 20
Temps Límit: 1.0s
Límit de memòria: 64M
Autor/a:
marc
tipus del problema
Cerca Binària, Programació Dinàmica
Categoria
Competitiu
Llenguatges permesos
Bash, C#, Haskell, Java, Kotlin, PHP, Python

aireacondicionat

David va a una fleca a comprar paninis, i diferents productes de pa, perquè a David li agrada el pa

A la fleca hi ha \(N\) diferents productes de pa, i cascun d'ells té un Preu \(P\) .

David va amb Chen a la fleca, compren \(M\) i Chen decideix dividir el cost per a cada producte de la següent forma.

Si el cost es menor a \(K\), David ho pagarà tot. Si el cost es superior a \(K\), David pagarà \(K\), i Chen pagarà la resta, és a dir, \(P-K\)

Assumim que \(D\) és el que pagarà David i \(C\) el que pagarà Chen. David no sap si Chen l'està estafant, així que intentarà buscar els productes per als quals la diferència \(D-C\) sigui el més petita possible. Ja que Chen no sap quants productes comprarà, David vol saber quina és la forma a on la diferència sigui millor per a ell per a \(Q\) diferents valors de \(K\) i \(M\)

Entrada

La primera línea conté dos enters, \(N\) i \(Q\) La segona línea conté \(N\) enters, els preus de cadascun dels productes de la fleca Després venen \(Q\) linies, cadascuna amb dos nombres, \(K\) i \(M\),

Sortida

S'imprimiran \(Q\) línies, cadascuna amb la expressió \(D-C\) més petita (és a dir, el cas més favorable per a David)

Exemple d'Entrada

5 2
1 9 22 10 19
18 4
5 2

Exemple de Sortida

34
-21

Explicació de l'exemple

En la primera línea, David pot agafar els productes amb cost 1,9,22 i 10. Pagarà 38 (1+9+18+10), i Chen 4 (22-18), per tant, 38-4 = 34 Fixa't que si agafés 19 en comptes de 10, pagaria (1+9+18+18) 46 i Chen 5 ((22-18)+(19-18)), per tant 41, que és més alt que 34.

En la segona línea, David agafa 22 i 19 i paga (5+5) 10, i Chen paga ((22-5)+(19-5)) 31, per tant, 10-31 = -21

Comentaris


  • -5
    EricMM8  comentat a les nov. 21, 2023, 5:04 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 5
      arnau  comentat a les nov. 21, 2023, 5:22 p.m.

      A ti lo que te da envidia es ver a un cliente satisfecho delante de una panadería que no es la tuya ;)


  • 7
    hector  comentat a les nov. 14, 2023, 5:07 p.m. ← editat

    David racista (Chen chino)


  • 5
    arnau  comentat a les nov. 14, 2023, 5:05 p.m.

    Chen, paga lo que le debes a David. Primer aviso.


    • 2
      DavidFeliciano  comentat a les set. 20, 2024, 11:38 p.m.

      Chen paga lo que me debes, segundo aviso


      • 1
        arnau  comentat a les oct. 8, 2024, 4:55 p.m.

        Chen, paga lo que le debes a David. Tercer aviso.


  • 5
    arnau  comentat a les nov. 14, 2023, 4:57 p.m.

    No es dejéis engañar: ese tipo destrozó Java y petó el JOEL una vez con su código terrorista (pero también arreglamos un bug, paradójicamente). onO


    • -7
      chchen  comentat a les nov. 14, 2023, 5:05 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


      • 3
        Themonster  comentat a les nov. 14, 2023, 5:08 p.m.

        中国人闭嘴


        • -2
          arnau  comentat a les nov. 14, 2023, 5:55 p.m.

          "¡Meowth, bien dicho!"


      • 2
        arnau  comentat a les nov. 14, 2023, 5:06 p.m.

        Pues cómete esta


    • 4
      Keita58  comentat a les nov. 14, 2023, 5:05 p.m.

      totalment cert