結果

問題 No.705 ゴミ拾い Hard
コンテスト
ユーザー 草苺奶昔
提出日時 2023-04-11 21:08:23
言語 Go
(1.23.4)
結果
AC  
実行時間 443 ms / 1,500 ms
コード長 4,832 bytes
コンパイル時間 12,762 ms
コンパイル使用メモリ 234,444 KB
実行使用メモリ 24,564 KB
最終ジャッジ日時 2024-10-07 15:49:14
合計ジャッジ時間 20,303 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

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

func main() {

	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n int
	fmt.Fscan(in, &n)
	A := make([]int, n)
	X := make([]int, n)
	Y := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &A[i])
	}
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &X[i])
	}
	for i := 0; i < n; i++ {
		fmt.Fscan(in, &Y[i])
	}
	f := func(i, j int) int {
		a := A[j-1]
		x := X[i]
		y := Y[i]
		dx := abs(a - x)
		dy := abs(y)
		return dx*dx*dx + dy*dy*dy
	}
	fmt.Fprintln(out, MongeShortestPath(n, f)[n])
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

const INF int = 1e18

func MongeShortestPath(N int, f func(i, j int) int) []int {
	dp := make([]int, N+1)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = 0
	larsch := NewLARSCH(N, func(i, j int) int {
		i++
		if i <= j {
			return INF
		}
		return dp[j] + f(j, i)
	})
	for r := 1; r <= N; r++ {
		l := larsch.GetArgmin()
		dp[r] = dp[l] + f(l, r)
	}
	return dp
}

// 检验[0,n]范围内的f是否满足Monge性质.
func CheckMonge(n int, f func(i, j int) int) bool {
	for l := 0; l <= n; l++ {
		for k := 0; k < l; k++ {
			for j := 0; j < k; j++ {
				for i := 0; i < j; i++ {
					lhs := f(i, l) + f(j, k)
					rhs := f(i, k) + f(j, l)
					if lhs < rhs {
						return false
					}
				}
			}
		}
	}
	return true
}

// ndp[j] = min(dp[i] + f(i,j))
func MongeDpUpdate(n int, dp []int, f func(i, j int) int) []int {
	if len(dp) != n+1 {
		panic("len(dp) != n+1")
	}
	choose := func(i, j, k int) int {
		if i <= k {
			return j
		}
		if dp[j]+f(j, i) > dp[k]+f(k, i) {
			return k
		}
		return j
	}
	I := _SMAWK(n+1, n+1, choose)
	ndp := make([]int, n+1)
	for i := range ndp {
		ndp[i] = INF
	}
	for j := range ndp {
		i := I[j]
		ndp[j] = dp[i] + f(i, j)
	}
	return ndp
}

// choose: func(i, j, k int) int 选择(i,j)和(i,k)中的哪一个(j or k)
//  返回值: minArg[i] 表示第i行的最小值的列号
func _SMAWK(H, W int, choose func(i, j, k int) int) (minArg []int) {
	var dfs func(X, Y []int) []int
	dfs = func(X, Y []int) []int {
		n := len(X)
		if n == 0 {
			return nil
		}
		YY := []int{}
		for _, y := range Y {
			for len(YY) > 0 {
				py := YY[len(YY)-1]
				x := X[len(YY)-1]
				if choose(x, py, y) == py {
					break
				}
				YY = YY[:len(YY)-1]
			}
			if len(YY) < len(X) {
				YY = append(YY, y)
			}
		}
		XX := []int{}
		for i := 1; i < len(X); i += 2 {
			XX = append(XX, X[i])
		}
		II := dfs(XX, YY)
		I := make([]int, n)
		for i, v := range II {
			I[i+i+1] = v
		}
		p := 0
		for i := 0; i < n; i += 2 {
			var lim int
			if i+1 == n {
				lim = Y[len(Y)-1]
			} else {
				lim = I[i+1]
			}
			best := Y[p]
			for Y[p] < lim {
				p++
				best = choose(X[i], best, Y[p])
			}
			I[i] = best
		}

		return I
	}

	X, Y := make([]int, H), make([]int, W)
	for i := range X {
		X[i] = i
	}
	for i := range Y {
		Y[i] = i
	}
	return dfs(X, Y)
}

type LARSCH struct {
	base *_reduceRow
}

func NewLARSCH(n int, f func(i, j int) int) *LARSCH {
	res := &LARSCH{base: newReduceRow(n)}
	res.base.setF(f)
	return res
}

func (l *LARSCH) GetArgmin() int {
	return l.base.getArgmin()
}

type _reduceRow struct {
	n      int
	f      func(i, j int) int
	curRow int
	state  int
	rec    *_reduceCol
}

func newReduceRow(n int) *_reduceRow {
	res := &_reduceRow{n: n}
	m := n / 2
	if m != 0 {

		res.rec = newReduceCol(m)
	}
	return res
}

func (r *_reduceRow) setF(f func(i, j int) int) {
	r.f = f
	if r.rec != nil {
		r.rec.setF(func(i, j int) int {
			return f(2*i+1, j)
		})
	}
}

func (r *_reduceRow) getArgmin() int {
	curRow := r.curRow
	r.curRow += 1
	if curRow%2 == 0 {
		prevArgmin := r.state
		var nextArgmin int
		if curRow+1 == r.n {
			nextArgmin = r.n - 1
		} else {
			nextArgmin = r.rec.getArgmin()
		}
		r.state = nextArgmin
		ret := prevArgmin
		for j := prevArgmin + 1; j <= nextArgmin; j += 1 {
			if r.f(curRow, ret) > r.f(curRow, j) {
				ret = j
			}
		}
		return ret
	}

	if r.f(curRow, r.state) <= r.f(curRow, curRow) {
		return r.state
	}
	return curRow
}

type _reduceCol struct {
	n      int
	f      func(i, j int) int
	curRow int
	cols   []int
	rec    *_reduceRow
}

func newReduceCol(n int) *_reduceCol {
	return &_reduceCol{n: n, rec: newReduceRow(n)}
}

func (c *_reduceCol) setF(f func(i, j int) int) {
	c.f = f
	c.rec.setF(func(i, j int) int {
		return f(i, c.cols[j])
	})
}

func (r *_reduceCol) getArgmin() int {
	curRow := r.curRow
	r.curRow += 1
	var cs []int
	if curRow == 0 {
		cs = []int{0}
	} else {
		cs = []int{2*curRow - 1, 2 * curRow}
	}

	for _, j := range cs {
		for {
			size := len(r.cols)
			flag := size != curRow && r.f(size-1, r.cols[size-1]) > r.f(size-1, j)
			if !flag {
				break
			}
			r.cols = r.cols[:size-1]
		}
		if len(r.cols) != r.n {
			r.cols = append(r.cols, j)
		}
	}
	return r.cols[r.rec.getArgmin()]
}
0