Fişierul intrare/ieşire:costsq.in, costsq.outSursăSelectie echipe ACM ICPC, UPB 2009
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test2.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Costsq

Se da o secventa cu N elemente: w(1), ..., w(N). Dorim sa impartim aceasta secventa in K subsecvente disjuncte (o subsecventa consta din elemente consecutive ale secventei date), in asa fel incat fiecare element al secventei apartine exact unei singure subsecvente. Notam prin S[i:j] subsecventa care incepe la pozitia i si se termina la pozitia j. Costul lui S[i:j] este (w(i)+w(i+1)+...+w(j))2. Costul unei impartiri in K subsecvente este egal cu suma costurilor celor K subsecvente. Determinati o impartire a secventei date in K subsecvente disjuncte, astfel incat costul impartirii sa fie minim.

In plus, se dau si o serie de constrangeri suplimentare. Daca din impartire face parte subsecventa S[i:j], atunci i trebuie sa respecte urmatoarele constrangeri: l(j) ≤ i ≤ u(j) (mai exact, daca alegem ca una din subsecvente sa se termine la pozitia j, atunci pozitia de inceput a subsecventei trebuie sa fie intre l(j) si u(j)). Valorile l(j) si u(j) au urmatoarele proprietati:

  • 1 ≤ l(j) ≤ u(j) ≤ j
  • l(j) ≤ l(j+1) (pentru 1 ≤ j ≤ N-1)
  • u(j) ≤ u(j+1) (pentru 1 ≤ j ≤ N-1)

Date de intrare

Prima linie a fisierului de intrare costsq.in contine numerele intregi N si K. Urmatoarele N linii descriu secventa data. A i-a dintre aceste linii contine valorile w(i), l(i) si u(i) (in aceasta ordine). Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de ieşire

În fişierul de ieşire costsq.out veti afisa costul total minim al unei impartiri a secventei date in K subsecvente care respecta constrangerile date. Se garanteaza ca va exista cel putin o impartire valida.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ K ≤ min{100,N}
  • 1 ≤ w(i) ≤ 1.000

Exemplu

costsq.incostsq.out
13 3
8 1 1
6 1 1
4 1 2
6 1 3
3 2 4
7 2 5
8 2 7
2 3 8
5 4 8
3 4 8
5 4 8
4 4 9
9 7 10
1642
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?