Hinded

시간 제한1초메모리 제한1024 MB

요약

N 곱하기 N 격자에 0부터 100까지의 점수가 주어질 때, 축에 나란한 직사각형 하나를 지워 남은 칸의 (점수 빼기 50) 합이 최대가 되도록 하는 값을 구한다.

난이도: 보통10점 중 7점
유형: 누적 합, 배열, 완전 탐색, 동적 계획법
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 1
입력
```
3
80 90 90
100 5 60
90 60 10
```
예상 출력
```
200
```

예제 2

입력

4
100 100 100 100
100 2 2 100
100 90 90 100
100 2 2 100

예상 출력