結果

問題 No.2549 Paint Eggs
コンテスト
ユーザー ID 21712
提出日時 2025-04-27 02:50:21
言語 Go
(1.23.4)
結果
AC  
実行時間 300 ms / 2,000 ms
コード長 1,287 bytes
コンパイル時間 13,499 ms
コンパイル使用メモリ 230,380 KB
実行使用メモリ 13,488 KB
最終ジャッジ日時 2025-04-27 02:50:48
合計ジャッジ時間 26,830 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "os"
import bf "bufio"
import "container/heap"

func main() {
	rd:=bf.NewReader(Stdin)
	var n,m,k int
	Fscan(rd,&n,&m,&k)
	c := make([]int, n)
	for i := range c {
		Fscan(rd,&c[i])
		c[i]--
	}
	a := make([]int, m)
	for i := range a {
		Fscan(rd,&a[i])
	}
	items := make([]*Item, m)
	pq := make(PQ, 0, m)
	for i := range items {
		items[i] = new(Item)
		items[i].color = i
		items[i].cost = a[i]*k
		heap.Push(&pq, items[i])
	}
	for _, v := range c[:k] {
		items[v].cost -= a[v]
		heap.Fix(&pq, items[v].index)
	}
	ans := pq[0].cost
	for i, j := 0, k; j < n; i,j=i+1,j+1 {
		ci, cj := c[i], c[j]
		items[ci].cost += a[ci]
		heap.Fix(&pq, items[ci].index)
		items[cj].cost -= a[cj]
		heap.Fix(&pq, items[cj].index)
		ans = min(ans, pq[0].cost)
	}
	Println(ans)
}

type Item struct {
	cost, color, index int
}

type PQ []*Item
func (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].cost < pq[j].cost }
func (pq PQ) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}
func (pq *PQ) Push(x any) {
	item := x.(*Item)
	item.index = pq.Len()
	*pq = append(*pq, item)
}
func (pq *PQ) Pop() any {
	old := *pq
	n := len(old)-1
	x := old[n]
	x.index = -1
	old[n] = nil
	*pq = old[:n]
	return x
}
0