Fişierul intrare/ieşire:spectacole.in, spectacole.outSursăAlgoritmiada 2015 Runda 1
AutorMarius Dumitran, Teodor PlopAdăugată deTeodor94Teodor Plop Teodor94
Timp execuţie pe test0.325 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Spectacole

Până şi Antonio a auzit de problema spectacolelor. Fiind însă o problemă deja foarte bine cunoscută şi mult prea "clasică" pentru gusturile lui Antonio, acesta vă propune să rezolvaţi următoarea problema a spectacolelor. Succes!

Se dau N săli de spectacole si M spectacole. Pentru fiecare din cele M spectacole se dau 3 numere si, xi si yi reprezentând sala unde se ţine spectacolul, timpul de început, respectiv timpul de sfârşit. Se ştie că pentru a se deplasa intre sali Antonio trebuie sa se deplaseze printr-o sală centrală, iar drumurile din această sală centrală spre o sală de spectacol şi drumurile inverse nu sunt identice. Mai exact durata de deplasare dinspre sala cu numarul i si sala centrală este Ai, iar dinspre sala centrală spre sala i este Bi. Nu exista altă metoda pentru Antonio să se deplaseze între 2 sali i şi j, astfel, pentru a se deplasa de la sala i la sala j Antonio are nevoie de Ai + Bj momente de timp. Antonio vrea să vadă cât mai multe spectacole, respectând următoarele reguli:

  • Antonio va vedea doar spectacole complete. Altfel spus, Antonio nu are voie să părăsească sala decât în momentul terminării spectacolului.
  • Dacă Antonio se află în sala i vizionând un spectacol care se termină la momentul de timp T, acesta are în continuare două opţiuni:
    • Poate rămâne în sala i, urmând să vizioneze după bunul său plac orice spectacol care începe la un moment de timp mai mare sau egal decât T.
    • Poate pleca la momentul T către oricare sală j (i diferit de j), ajungând în sala j la momentul de timp T + Ai + Bj. Astfel, acesta poate viziona orice spectacol care rulează în sala j şi are timpul de început mai mare sau egal cu T + Ai + Bj.

Date de intrare

Fişierul de intrare spectacole.in conţine două numere naturale N şi M, reprezentând numărul sălilor de spectacol, respectiv numarul de spectacole. Urmatorul rand va contine N numere reprezentand valorile A1, A2, ..., respectiv AN. Al treilea rand va contine inca N numere reprezentand valorile B1, B2, ..., respectiv BN.
Urmatoarele M linii vor contine cate 3 valori intregi fiecare. A i-a dintre aceste linii va contine valorile si, xi si yi.

Date de ieşire

În fişierul de ieşire spectacole.out se va găsi un singur număr natural, reprezentând numărul maxim de spectacole pe care le poate vedea Antonio, respectând regulile de mai sus.

Restricţii

  • 1 ≤ N ≤ 2000
  • 1 ≤ M ≤ 20000
  • 1 ≤ si ≤ N
  • 0 ≤ xi < yi ≤ 1.000.000.000
  • 0 ≤ Ai, Bi ≤ 1.000.000.000
  • Se garantează că nu există două spectacole care să ruleze simultan în aceeaşi sală.
  • Pentru teste in valoare de 30 de puncte N ≤ 100 si yi ≤ 1.250
  • Pentru teste in valoare de inca 20 de puncte N ≤ 500 si yi ≤ 1.250
  • Pentru teste in valoare de 20 de puncte (dar nu neaparat altele decat cele 30 + 20 de mai sus) Ai = Bi = 0

Exemplu

spectacole.inspectacole.out
2 4
2 2
3 3
1 0 5
1 5 13
2 10 15
2 15 20
3

Explicaţie

Antonio va viziona primul spectacol care are loc in sala 1. La momentul de timp 5 va pleca către sala 2, unde va viziona spectacolele 3 si 4.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?