Fişierul intrare/ieşire:metrouri.in, metrouri.outSursăLot Arad 2011
AutorTiberiu SavinAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Metrouri

În Ţara lui Stuf-Vodă există o linie de metrou cu N staţii, numerotate cu 1, 2, …, N plasate pe o dreaptă la distanţe egale, de la stânga la dreapta. MetroStuf dispune de K metrouri care circulă pe această linie. Acestea pleacă din staţia 1 către staţia N. Timpul de deplasare a unui metrou între două staţii consecutive este de un minut.

Stuf-Vodă vrea însă să îşi ţină oameni cât mai fericiţi, aşa că vrea să găsească un scenariu optim de plecare a metrourilor din staţia 1 către staţia N, astfel încât oameni să aştepte cât mai puţin. Se dau M perechi de forma (Si, Ti) cu semnificaţia: în staţia Si la minutul Ti ajunge o persoană. Se defineşte costul unui metrou, ca fiind timpul cel mai mare de aşteptare al unei persoane, care s-a urcat în metroul respectiv. Stuf-Vodă şi-a dat seama că oamenii din ţara lui sunt cu atât mai fericiţi cu cât suma costurilor metrourilor este mai mică. O persoană urcă întotdeauna în primul metrou care soseşte în staţie.

Dându-se N, M, K şi M perechi de forma (Si, Ti) cu semnificaţia de mai sus, se cere să se calculeze momentele de timp la care trebuie să plece metrourile din staţia 1 către staţia N, astfel încât suma costurilor metrourilor să fie minimă.

Date de intrare

Pe prima linie a fişierului metrouri.in se vor găsi trei numere: N, M şi K separate prin câte un spaţiu, cu semnificaţia din enunţ. Pe următoarele M linii se vor găsi câte două numere, Si şi Ti, cu semnificaţia că la momentul de timp Ti în staţia Si ajunge o persoană.

Date de ieşire

Fisierului de ieşire metrouri.out va conţine un singur număr şi anume suma costurilor celor K metrouri.

Restricţii

  • 1 ≤ N, M, K ≤ 100 000
  • Metrourile nu merg decât într-un singur sens şi odată ajunse în staţia N rămân acolo până la sfârşitul zilei
  • Pentru 30% din teste N ≤ 200, M ≤ 1000, K ≤ 100
  • Pentru 60% din teste N ≤ 10 000, M ≤ 20 000, K ≤ 300
  • 1 ≤ Si ≤ N
  • 0 ≤ Ti ≤ 1 000 000
  • MetroStuf se deschide la minutul 0 (persoanele nu pot ajunge mai devreme de aceasta ora în staţii), însă metrourile pot pleca din staţia 1 înainte de acest moment.
  • În oricare metrou pot să urce oricâte persoane.

Exemplu

metrouri.inmetrouri.out
5 5 3
1 5
2 7
1 8
5 6
4 4
2

Explicaţie

Metroul 1 pleacă din staţia 1 la minutul 2, metroul 2 pleacă la minutul 6, iar metroul 3 la minutul 8. Costul metroului 1 este 1, costului metroului 2 este 1, iar costul metroului 3 este 0. Suma costurilor metrourilor este 2.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content