結果

問題 No.1345 Beautiful BINGO
ユーザー 小野寺健小野寺健
提出日時 2021-12-17 14:48:06
言語 Go
(1.23.4)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 2,144 bytes
コンパイル時間 21,810 ms
コンパイル使用メモリ 249,352 KB
実行使用メモリ 6,656 KB
最終ジャッジ日時 2025-01-18 04:04:38
合計ジャッジ時間 52,377 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 60 TLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"fmt"
	"bufio"
	"os"
	"sort"
	"math"
)

type Row struct {
	row map[int]bool
	diag map[int]bool
	cnt int
	col []int
	size int
}

func (this *Row) new(n int) {
	this.cnt = 0
	this.col = make([]int, n)
	this.size = 0
	this.row = make(map[int]bool)
	this.diag = make(map[int]bool)
}

func (this *Row) SetCol(A [][]int) {
	for i := 0; i < len(this.col); i++ {
		for j, _ := range this.row {
			if !this.ContainDiag(j, i) {
				this.col[i] += A[j][i]
			}
		}
	}
	sort.Ints(this.col)
	for i := 0; i < len(this.col)-1; i++ {
		this.col[i+1] += this.col[i]
	}
}

func (this *Row) SetDiag(row int, col int) {
	i := (row << 16) + col
	if _, ok := this.diag[i]; !ok {
		this.diag[i] = true
	}
}

func (this *Row) ContainDiag(row int, col int) bool {
	i := (row << 16) + col
	_, ok := this.diag[i]
	return ok
}

func Min(a int, b int) int {
	if a <= b {
		return a
	} else {
		return b
	}
}

func main() {
	r := bufio.NewReader(os.Stdin)
	w := bufio.NewWriter(os.Stdout)
    defer w.Flush()
	var N, M int
	fmt.Fscan(r, &N, &M)
	var RowSum []int = make([]int, N)
	var A [][]int = make([][]int, N)
	for i := 0; i < N; i++ {
		A[i] = make([]int, N)
		sum := 0
		for j := 0; j < N; j++ {
			var a int
			fmt.Fscan(r, &a)
			sum += a
			A[i][j] = a
		}
		RowSum[i] = sum
	}
	var ans int = math.MaxInt64
	for i := 0; i < 1 << (N+2); i++ {
		row := new(Row)
		row.new(N)
		for j := 0; j < N; j++ {
			if (i & (1 << j)) != 0 {
				row.cnt += RowSum[j]
				row.size++
			} else {
				row.row[j] = true
			}
		}
		if (i & (3 << N)) != 0 {
			for j := 0; j < N; j++ {
				if _, ok := row.row[j]; ok {
					if (i & (1 << N)) != 0 {
						row.cnt += A[j][j]
						row.SetDiag(j, j)
					}
					if (i & (1 << (N+1))) != 0 {
						if !row.ContainDiag(j, N-1-j) {
							row.cnt += A[j][N-1-j]
							row.SetDiag(j, N-1-j)
						}
					}
				}
			}
			if (i & (1 << N)) != 0 {
				row.size++
			}
			if (i & (1 << (N+1))) != 0 {
				row.size++
			}
		}
		row.SetCol(A)
		if row.size == M {
			ans = Min(ans, row.cnt)
		} else if (row.size < M && M - row.size <= N) {
			ans = Min(ans, row.cnt + row.col[M-row.size-1])
		}
	}
	fmt.Fprintln(w, ans)
}
0