← Home
For problem statement at 1000-1999/1200-1299/1210-1219/1219/problemG.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1210-1219/1219/verifierG.go ends with All 120 tests passed can you fix the verifier? package main

import (
	"bufio"
	"io"
	"os"
)

func top4Sum(a []int64) int64 {
	var x1, x2, x3, x4 int64
	for _, v := range a {
		if v >= x1 {
			x4 = x3
			x3 = x2
			x2 = x1
			x1 = v
		} else if v >= x2 {
			x4 = x3
			x3 = x2
			x2 = v
		} else if v >= x3 {
			x4 = x3
			x3 = v
		} else if v > x4 {
			x4 = v
		}
	}
	return x1 + x2 + x3 + x4
}

func writeInt64(w *bufio.Writer, x int64) {
	if x == 0 {
		w.WriteByte('0')
		w.WriteByte('\n')
		return
	}
	var buf [20]byte
	i := len(buf)
	for x > 0 {
		i--
		buf[i] = byte(x%10) + '0'
		x /= 10
	}
	w.Write(buf[i:])
	w.WriteByte('\n')
}

func main() {
	input, _ := io.ReadAll(os.Stdin)
	idx := 0
	nextInt := func() int64 {
		for idx < len(input) && (input[idx] < '0' || input[idx] > '9') {
			idx++
		}
		var n int64
		for idx < len(input) && input[idx] >= '0' && input[idx] <= '9' {
			n = n*10 + int64(input[idx]-'0')
			idx++
		}
		return n
	}

	N := int(nextInt())
	M := int(nextInt())

	data := make([]int64, N*M)
	rowSum := make([]int64, N)
	colSum := make([]int64, M)
	var total int64

	for i := 0; i < N; i++ {
		base := i * M
		for j := 0; j < M; j++ {
			v := nextInt()
			data[base+j] = v
			rowSum[i] += v
			colSum[j] += v
			total += v
		}
	}

	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	if N+M <= 4 {
		writeInt64(out, total)
		return
	}

	var ans int64

	if N >= 4 {
		v := top4Sum(rowSum)
		if v > ans {
			ans = v
		}
	}

	if M >= 4 {
		v := top4Sum(colSum)
		if v > ans {
			ans = v
		}
	}

	if N >= 1 && M >= 3 {
		for i := 0; i < N; i++ {
			base := i * M
			var x1, x2, x3 int64
			for j := 0; j < M; j++ {
				v := colSum[j] - data[base+j]
				if v >= x1 {
					x3 = x2
					x2 = x1
					x1 = v
				} else if v >= x2 {
					x3 = x2
					x2 = v
				} else if v > x3 {
					x3 = v
				}
			}
			v := rowSum[i] + x1 + x2 + x3
			if v > ans {
				ans = v
			}
		}
	}

	if N >= 3 && M >= 1 {
		for j := 0; j < M; j++ {
			var x1, x2, x3 int64
			for i := 0; i < N; i++ {
				v := rowSum[i] - data[i*M+j]
				if v >= x1 {
					x3 = x2
					x2 = x1
					x1 = v
				} else if v >= x2 {
					x3 = x2
					x2 = v
				} else if v > x3 {
					x3 = v
				}
			}
			v := colSum[j] + x1 + x2 + x3
			if v > ans {
				ans = v
			}
		}
	}

	if N >= 2 && M >= 2 {
		if N <= M {
			for a := 0; a < N; a++ {
				baseA := a * M
				for b := a + 1; b < N; b++ {
					baseB := b * M
					var x1, x2 int64
					for j := 0; j < M; j++ {
						v := colSum[j] - data[baseA+j] - data[baseB+j]
						if v >= x1 {
							x2 = x1
							x1 = v
						} else if v > x2 {
							x2 = v
						}
					}
					v := rowSum[a] + rowSum[b] + x1 + x2
					if v > ans {
						ans = v
					}
				}
			}
		} else {
			for a := 0; a < M; a++ {
				for b := a + 1; b < M; b++ {
					var x1, x2 int64
					for i := 0; i < N; i++ {
						v := rowSum[i] - data[i*M+a] - data[i*M+b]
						if v >= x1 {
							x2 = x1
							x1 = v
						} else if v > x2 {
							x2 = v
						}
					}
					v := colSum[a] + colSum[b] + x1 + x2
					if v > ans {
						ans = v
					}
				}
			}
		}
	}

	writeInt64(out, ans)
}