| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1.5 초 | 1024 MB | 4 | 2 | 2 | 100.000% |
$N$ personer ska delas in i grupper. Varje person ska vara med i exakt en grupp, och varje grupp ska ha exakt en ledare. Varje person har tre heltal som beskriver deras ledaregenskaper: $a_i$, $b_i$ och $c_i$. Person nummer $i$ kan vara ledare för en grupp med $x \le c_i$ personer (om $c_i=1$ måste person $i$ vara helt ensam i sin grupp om hen ska vara ledare). Gruppens styrka definieras då som heltalet $a_i\cdot x + b_i$. Din uppgift är att dela in personerna i grupper så att summan av styrkorna hos grupperna maximeras.
Den första raden av indata innehåller ett heltal $N$ ($1 \le N \le 4000$): antalet personer.
Därefter följer $N$ rader med tre heltal vardera: $a_i$, $b_i$ och $c_i$ ($-10^9 \le a_i, b_i \le 10^9$, $1 \le c_i \le N$).
Skriv ut ett tal: den största summa av styrkor som kan uppnås.
5 10 7 2 -1 20 4 5 10 3 2 2 2 2 2 2
66
5 6 -40 4 7 -40 4 10 -20 2 11 -30 3 12 -10 1
3
4 1000000000 1000000000 2 -1000000000 10 2 900000000 -1000000000 2 -20 -25 1
3800000000
I det första exemplet kan den högsta styrka uppnås t.ex. genom att dela in personerna i tre grupper: en bestående av person 1 och 4 (med 1 som ledare), en med person 3 och 5 (med 3 som ledare), och en med person 2. Detta ger $(10 \cdot 2 + 7) + (-1 \cdot 1 + 20) + (5 \cdot 2 + 10) = 66$ styrka. Testfallet skulle kunna finnas med i testgrupp 3.
I det andra exemplet kan högsta styrka uppnås t.ex. genom att dela in personerna i två grupper: en med personer 1, 2 och 3 (med 3 som ledare), och en med personer 4 och 5 (med 4 som ledare). Detta ger $(10 \cdot 2 + -20) + (11 \cdot 3 + -30) = 3$ styrka. Testfallet skulle kunnas finnas med i testgrupp 4.
Olympiad > Swedish Olympiad in Informatics > 2021 > KATT ?번