369 Import

[•danielp]

Aici puteţi discuta despre problema Import.

[•devilkind]

iau 20 de pct cu WA pe restu si nu inteleg de ce.
Adik eu notez cu S[ i] suma nodurilor de la 1 la i si de iar  numerele de la k+1 la n numere le consider inmulteste cu -1. Astfel reduc problema la constrangeri cu diferente. Ptr o operatie de tipul a b x 0 bag in graful de constrangeri o muchie de la a la b de cost -1*x ca sa am semnul constrangerii <= iar dak tipul este 1 atunci bag muchia de la b la a de cost x-1 (ptr ca tre sa fie strict mai mic). Ce ar putea fi??

[•filipb]

Se obtin 20 de puncte daca consideri radacina ( nodul 1 ) atat in prima, cat si in a doua multime. Pentru a rezolva problema, poti considera radacina doar in primele K, de exemplu. Astfel, primele K numere din S, S(i), vor fi suma nodurilor de la 1 la i, inclusiv 1, iar celelalte numere, S[j], j > K, suma nodurilor de la 1 la j, fara 1.