結果

問題 No.866 レベルKの正方形
コンテスト
ユーザー ccppjsrb
提出日時 2020-06-09 22:55:09
言語 Go
(1.23.4)
結果
TLE  
実行時間 -
コード長 2,753 bytes
コンパイル時間 14,334 ms
コンパイル使用メモリ 234,576 KB
実行使用メモリ 422,432 KB
最終ジャッジ日時 2025-01-03 02:45:35
合計ジャッジ時間 115,924 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 8 TLE * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func configure(scanner *bufio.Scanner) {
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 1000005), 1000005)
}
func getNextString(scanner *bufio.Scanner) string {
	scanned := scanner.Scan()
	if !scanned {
		panic("scan failed")
	}
	return scanner.Text()
}
func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}
func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}
func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}
func main() {
	fp := os.Stdin
	wfp := os.Stdout
	extra := 0
	if os.Getenv("I") == "IronMan" {
		fp, _ = os.Open(os.Getenv("END_GAME"))
		extra = 100
	}
	scanner := bufio.NewScanner(fp)
	configure(scanner)
	writer := bufio.NewWriter(wfp)
	defer func() {
		r := recover()
		if r != nil {
			fmt.Fprintln(writer, r)
		}
		writer.Flush()
	}()
	solve(scanner, writer)
	for i := 0; i < extra; i++ {
		fmt.Fprintln(writer, "-----------------------------------")
		solve(scanner, writer)
	}
}
func solve(scanner *bufio.Scanner, writer *bufio.Writer) {
	h := getNextInt(scanner)
	w := getNextInt(scanner)
	k := getNextInt(scanner)
	ss := make([]string, h)
	for i := 0; i < h; i++ {
		ss[i] = getNextString(scanner)
	}
	imim := make([]imos, 26)
	for i := 0; i < 26; i++ {
		imim[i] = newImos(h, w, byte('a'+i), ss)
	}
	var ans int
	for y := 0; y < h; y++ {
		for x := 0; x < w; x++ {
			lowers := make([]int, 2)
			for lw := 0; lw < 2; lw++ {
				l := 0
				r := min(h-y, w-x) + 1
				for 1 < r-l {
					m := (l + r) >> 1
					cnt := 0
					for i := 0; i < 26; i++ {
						if imim[i].count(y, x, y+m, x+m) > 0 {
							cnt++
						}
					}
					if cnt < k+lw {
						l = m
						continue
					}
					r = m
				}
				lowers[lw] = r
			}
			ans += lowers[1] - lowers[0]
		}
	}
	fmt.Fprintln(writer, ans)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

type imos struct {
	c [][]int32
}

func newImos(h, w int, ch byte, ss []string) imos {
	c := makeGrid(h+1, w+1)
	for y := 0; y < h; y++ {
		for x := 0; x < w; x++ {
			if ss[y][x] == ch {
				c[y+1][x+1] = 1
			}
		}
	}
	for y := 0; y < h; y++ {
		for x := 0; x < w; x++ {
			c[y+1][x+1] += c[y+1][x]
		}
	}
	for x := 0; x < w; x++ {
		for y := 0; y < h; y++ {
			c[y+1][x+1] += c[y][x+1]
		}
	}
	return imos{
		c: c,
	}
}

func (im *imos) count(fy, fx, ty, tx int) int32 {
	return im.c[ty][tx] - im.c[ty][fx] - im.c[fy][tx] + im.c[fy][fx]
}
func makeGrid(h, w int) [][]int32 {
	index := make([][]int32, h, h)
	data := make([]int32, h*w, h*w)
	for i := 0; i < h; i++ {
		index[i] = data[i*w : (i+1)*w]
	}
	return index
}
0