시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.000%

문제

Linna ehitatakse uut kaubanduskeskust, mille põhiplaan koosneb $N \times M$ ühikruudust. Ruut $(1, 1)$ on keskuse loodenurgas ja ruut $(N, M)$ kagunurgas. Kuigi keskust alles ehitatakse, on turundajad juba hinnanud, et ruutu $(i, j)$ hakkab päevas külastama $A_{ij}$ ostjat.

Keskuses tahavad oma poed avada $K$ firmat, mis on nummerdatud $1 \ldots K$. Iga pood võib paikneda ühes või mitmes ruudus, aga peab olema 4-sidus: poe igast ruudust peab pääsema poe igasse teise ruutu, läbides teel ainult selle poe ruute ja astudes igal sammul ühest ruudust teise üle nende ühise serva. Loomulikult ei saa ühes ruudus olla mitut poodi. Lisaks ei luba ohutusnõuded teha keskusse poodi, mis on suurem kui $S$ ruutu.

Kaubanduskeskuse juhataja tahab pakkuda poodidele pindu nii, et nende alla jäävate ruutude külastatavuste summa oleks võimalikult suur (vähemkülastatavad ruudud jäävad koridorideks ja muudeks abiruumideks). Aita turundusjuhil koostada võimalikult hea pakkumine.

입력

Sisendfaili esimesel real on testi number $T$.

Faili teisel real on neli täisarvu $N$, $M$, $K$ ja $S$: keskuse laius ja pikkus, poodide arv ja poe maksimaalne suurus.

Järgmisel $N$ real on igaühel täpselt $M$ täisarvu $A_{ij}$: keskuse ruutude külastatavused.

Faili viimasel real on täisarv $Y$: poodide summaarne külastatavus žürii lahenduses.

출력

Väljundfaili esimesele reale väljastada testi number $T$.

Järgmisele $N$ reale väljastada igaühele täpselt $M$ täisarvu $B_{ij}$ ($0 \le B_{ij} \le K$), kus $B_{ij} > 0$ näitab vastaval ruudul asuva poe omaniku numbrit ja $B_{ij} = 0$ tähistab vabaks jäävat ruutu.

채점

Selles ülesandes on (testimiskeskkona kaudu) antud 10 sisendfaili (input_001.txt kuni input_010.txt) ja lahendusena tuleb esitada neile vastavad väljundfailid (output_001.txt kuni output_010.txt). Programmi esitamine pole vajalik ja seda ei hinnata.

Väljundfail, mille vorming või milles kirjeldatav poodide paigutus ei vasta ülesande tingimustele, teenib 0 punkti. Korrektne fail teenib $$ \min\left( 10, 10 \cdot \left(\frac{X}{Y}\right)^2 \right) $$ punkti, kus $X$ on poodide summaarne külastatavus failis kirjeldatud paigutuse korral ja $Y$ on summaarne külastatavus žürii lahenduses.

예제 입력 1

0
4 9 2 8
1 7 6 4 2 1 2 1 2
2 5 2 3 1 2 5 3 7
1 8 5 4 2 1 5 1 8
1 2 3 1 2 2 1 2 5
79

예제 출력 1

0
0 1 1 1 0 0 2 0 0
0 1 0 1 0 2 2 2 2
0 1 1 1 0 0 2 0 2
0 0 0 0 0 0 0 0 2

Poodide summaarne külastatavus on $(7 + 6 + 4 + 5 + 3 + 8 + 5 + 4) + (2 + 2 + 5 + 3 + 7 + 5 + 8 + 5) = 42 + 37 = 79$.

채점 및 기타 정보

  • 100점 이상을 획득해야 를 받는다.
  • 예제는 채점하지 않는다.