28712번 - Trobojnica 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 24 | 20 | 15 | 78.947% |
문제
Moje zastave uvijek su iste boje... crveno-bijelo-plave.
Fifi voli bojati zastave sa zanimljivim svojstvima. Nakon što je navio alarm za sljedeći dan, odlučio je prije spavanja obojati još jednu zastavu.
Njegova zastava ima visinu $n$ i širinu $m$, a polje u $i$-tom retku i $j$-tom stupcu ima sklonost $c_{i,j}$ crvenoj boji, $b_{i,j}$ bijeloj boji, i $p_{i,j}$ plavoj boji.
Fifi boja zastavu stupac po stupac: najprije oboji nekoliko polja u crvenu boju, zatim nekoliko u bijelu boju, a ostatak u plavu boju, točno tim redom gledano s vrha stupca prema dnu. Svaki stupac mora imati barem po jedno polje crvene, bijele i plave boje.
Pritom želi maksimizirati ostvarene sklonosti, tj. želi da je sljedeći zbroj najveći mogući:
- Ako je polje u $i$-tom retku $j$-tog stupca obojano u crvenu boju, tada se ukupna ostvarena sklonost povećava za $c_{i,j}$.
- Ako je polje u $i$-tom retku $j$-tog stupca obojano u bijelu boju, tada se ukupna ostvarena sklonost povećava za $b_{i,j}$.
- Ako je polje u $i$-tom retku $j$-tog stupca obojano u plavu boju, tada se ukupna ostvarena sklonost povećava za $p_{i,j}$.
Odredite maksimalnu ostvarenu sklonost.
입력
U prvom retku su prirodni brojevi $n$ i $m$ ($3 ≤ n ≤ 2\,500$, $1 ≤ m ≤ 2\,500$), visina i širina zastave.
Slijedi $n$ redatka po $m$ cijelih brojeva $c_{i,j}$ ($0 ≤ c_{i,j} ≤ 1\,000$), gdje $c_{i,j}$ predstavlja sklonost crvenoj boji polja u $i$-tom retku i $j$-tom stupcu.
Slijedi $n$ redatka po $m$ cijelih brojeva $b_{i,j}$ ($0 ≤ b_{i,j} ≤ 1\,000$), gdje $b_{i,j}$ predstavlja sklonost bijeloj boji polja u $i$-tom retku i $j$-tom stupcu.
Slijedi $n$ redatka po $m$ cijelih brojeva $p_{i,j}$ ($0 ≤ p_{i,j} ≤ 1\,000$), gdje $p_{i,j}$ predstavlja sklonost plavoj boji polja u $i$-tom retku i $j$-tom stupcu.
출력
U prvi i jedini redak ispišite traženi broj.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 13 | $n = 3$ |
| 2 | 21 | $n, m ≤ 50$ |
| 3 | 29 | $n, m ≤ 500$ |
| 4 | 37 | Nema dodatnih ograničenja. |
예제 입력 1
3 1 2 2 2 4 4 4 1 1 1
예제 출력 1
7
예제 입력 2
5 3 4 4 2 2 3 1 3 2 1000 0 1000 5 7 2 5 100 256 126 783 144 231 45 12 65 189 132 43 126 672 90 67 12 54 14 63 78 24 73 26 37 85 62 43 25 39
예제 출력 2
2480
예제 입력 3
4 2 0 0 0 0 0 0 0 0 2 4 3 6 1 7 8 2 7 2 9 6 4 3 7 1
예제 출력 3
28
힌트
Pojašnjenja probnih primjera: Lijevo je prikaz bojanja zastave prvog probnom prijema, u sredini drugog probnog prijema, i desno trećeg probnog primjera.
출처
Olympiad > Croatian Highschool Competitions in Informatics > 2023 > Croatian Olympiad in Informatics for Girls 2023 3번
채점 및 기타 정보
- 예제는 채점하지 않는다.