costsq

Costsq

== include(page="template/taskheader" task_id="costsq") ==

Poveste şi cerinţă...

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$)

h2. Date de intrare

Fişierul de intrare $costsq.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $costsq.out$ ...

Î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.

h2. Restricţii

* $... ≤ ... ≤ ...$

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

h2. Exemplu
table(example). |_. costsq.in |_. costsq.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|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

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="costsq") ==