結果

問題 No.2509 Beam Shateki
コンテスト
ユーザー ID 21712
提出日時 2025-05-02 18:50:15
言語 Go
(1.23.4)
結果
WA  
実行時間 -
コード長 2,167 bytes
コンパイル時間 12,796 ms
コンパイル使用メモリ 236,360 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-02 18:50:32
合計ジャッジ時間 15,155 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 60 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"

func main() {
	var h, w int
	Scan(&h, &w)
	grid := make([][]int, h+2)
	for i := range grid {
		grid[i] = make([]int, w+2)
	}
	for i := 1; i <= h; i++ {
		for j := 1; j <= w; j++ {
			Scan(&grid[i][j])
		}
	}
	dt := []int{0, -1, 0, 1, -1, -1, 1, 1, 0}
	type Beam struct {
		score int
		y0, x0 int
		dy, dx int
	}
	beams := []*Beam{}
	for y0 := 0; y0 < h+2; y0++ {
		for x0 := 0; x0 < w+2; x0 += w+1 {
			for di, dx := range dt[1:] {
				dy := dt[di]
				score := 0
				y, x := y0, x0
				for {
					y, x = y+dy, x+dx
					if y < 1 || h < y || x < 1 || w < x {
						break
					}
					score += grid[y][x]
				}
				if score == 0 {
					continue
				}
				beams = append(beams, &Beam{
					score: score,
					y0: y0,
					x0: x0,
					dy: dy,
					dx: dx,
				})
			}
		}
	}
	for y0 := 0; y0 < h+2; y0 += h+1 {
		for x0 := 0; x0 < w+2; x0++ {
			for di, dx := range dt[1:] {
				dy := dt[di]
				score := 0
				y, x := y0, x0
				for {
					y, x = y+dy, x+dx
					if y < 1 || h < y || x < 1 || w < x {
						break
					}
					score += grid[y][x]
				}
				if score == 0 {
					continue
				}
				beams = append(beams, &Beam{
					score: score,
					y0: y0,
					x0: x0,
					dy: dy,
					dx: dx,
				})
			}
		}
	}
	var ans int
	for i, beam1 := range beams {
		ans = max(ans, beam1.score)
		for _, beam2 := range beams[i+1:] {
			var x, y int
			if k := beam2.dy*beam1.dx-beam1.dy*beam2.dx; k != 0 {
				y = beam2.dy*beam1.dx*beam1.y0 -
					beam1.dy*beam2.dx*beam2.y0 +
					beam1.dy*beam2.dy*(beam2.x0-beam1.x0)
				if y % k == 0 {
					y /= k
				} else {
					continue
				}
			}
			if k := beam2.dx*beam1.dy-beam1.dx*beam2.dy; k != 0 {
				x = beam2.dx*beam1.dx*(beam2.y0-beam1.y0) +
					beam2.dx*beam1.dy*beam1.x0 -
					beam1.dx*beam2.dy*beam2.x0
				if x % k == 0 {
					x /= k
				} else {
					continue
				}
			}
			score := beam1.score + beam2.score
			if 1 <= y && y <= h && 1 <= x && x <= w {
				ans = max(ans, score - grid[y][x])
			} else if beam1.dx*(beam2.y0-beam1.y0) != beam1.dy*(beam2.x0-beam1.x0) || beam2.dx*(beam1.y0-beam2.y0) != beam2.dy*(beam1.x0-beam2.x0) {
				ans = max(ans, score)
			}
		}
	}
	Println(ans)
}
0