結果

問題 No.3417 Tired Santa
コンテスト
ユーザー ID 21712
提出日時 2025-12-24 13:46:14
言語 Go
(1.23.4)
結果
AC  
実行時間 23 ms / 2,000 ms
コード長 1,390 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 12,763 ms
コンパイル使用メモリ 239,900 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-12-24 13:46:29
合計ジャッジ時間 13,751 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

func main() {
	var n, s int
	Scan(&n, &s)
	xs := make([]int, n)
	ws := make([]int, n)
	fp := 0 // スタート地点の右隣の地点index
	for i := range xs {
		Scan(&xs[i])
		if s > xs[i] {
			fp = i+1
		}
	}
	total := 0
	for i := range ws {
		Scan(&ws[i])
		total += ws[i]
	}
	const XXX = 1 << 60
	cs := make([]int, n)
	ts := make([]int, n)
	for i := range cs {
		cs[i] = XXX
	}
	if fp-1 >= 0 {
		cs[fp-1] = (s - xs[fp-1]) * total
		ts[fp-1] = total - ws[fp-1]
	}
	if fp < n {
		cs[fp] = (xs[fp] - s) * total
		ts[fp] = total - ws[fp]
	}
	nxcs := make([]int, n)
	nxts := make([]int, n)
	for k := 1; k < n; k++ {
		for i := range nxcs {
			nxcs[i] = XXX
			nxts[i] = 0
		}
		for i, c := range cs {
			if c == XXX {
				continue
			}
			if i < fp {
				if i-1 >= 0 {
					cost := (xs[i]-xs[i-1])*ts[i]
					nxcs[i-1] = min(nxcs[i-1], c+cost)
					nxts[i-1] = ts[i]-ws[i-1]
				}
				if j := i+k; j < n {
					cost := (xs[j]-xs[i])*ts[i]
					nxcs[j] = min(nxcs[j], c+cost)
					nxts[j] = ts[i]-ws[j]
				}
			} else {
				if i+1 < n {
					cost := (xs[i+1]-xs[i])*ts[i]
					nxcs[i+1] = min(nxcs[i+1], c+cost)
					nxts[i+1] = ts[i]-ws[i+1]
				}
				if j := i-k; j >= 0 {
					cost := (xs[i]-xs[j])*ts[i]
					nxcs[j] = min(nxcs[j], c+cost)
					nxts[j] = ts[i]-ws[j]
				}
			}
		}
		cs,nxcs = nxcs,cs
		ts,nxts = nxts,ts
	}
	Println(min(cs[0], cs[n-1]))
}
0