| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 2 | 2 | 2 | 100.000% |
Juku on koolis teinud hulga kontrolltöid, mida hinnati 0ドル \ldots 100$ punktiga.
Juku vanaisa annab talle hinnete eest taskuraha. Vanaisa loeb tulemused üle 50ドル$ punkti headeks hinneteks ja tulemused alla 50ドル$ punkti halbadeks hinneteks. Täpsemalt liidab ta hinnete 50ドル$ punkti ületavad osad Juku taskurahale ning lahutab 50ドル$ punkti alla jäävad osad sealt maha. Näiteks hinnete 35ドル,ドル 42ドル,ドル 81ドル$ ja 100ドル$ eest saaks Juku kokku $(35-50)+(42-50)+(81-50)+(100-50) = -15-8+31+50 = 58$ eurot. (Täpselt 50ドル$ punktiga hinnatud tööd seega taskuraha ei mõjuta.)
Õpetaja hoiab Juku hindeid $N$ rea ja $N$ veeruga Exceli tabelis. Kokku on Jukul seega $N^2$ hinnet. Juku pääseb tabelile korraks ligi ja tal on võimalus oma hindeid "parandada" sel viisil, et ta märgib tabelis ühe ristkülikukujulise alamosa (mis võib olla ka tühi, s.t. sisaldada null elementi) ja kustutab sealt kõik hinded.
Leida, mis on maksimaalne hulk taskuraha, mille Juku võiks sellise kustutamise järel saada.
Sisendi esimesel real on täisarv $N$ (2ドル \le N \le 300$): õpetaja tabeli küljepikkus.
Järgmisel $N$ real on igaühel $N$ tühikutega eraldatud täisarvu lõigust 0ドル \ldots 100$: Juku hinded.
Väljundisse kirjutada üks täisarv: Juku maksimaalse taskuraha summa.
3 80 90 90 100 5 60 90 60 10
200
Juku peaks kustutama hinded 5ドル,ドル 60ドル,ドル 60ドル,ドル 10ドル$ tabeli alumisest paremast osast.
4 100 100 100 100 100 2 2 100 100 90 90 100 100 2 2 100
500
Juku peaks kustutama kõik hinded 2ドル$ ja 90ドル$.