← Home
For problem statement at 0-999/600-699/620-629/627/problemC.txt this is a correct solution, but verifier at 0-999/600-699/620-629/627/verifierC.go ends with  can you fix the verifier? package main

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

type Station struct {
	x int64
	p int64
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var d, n int64
	var m int
	if _, err := fmt.Fscan(reader, &d, &n, &m); err != nil {
		return
	}

	stations := make([]Station, m+2)
	stations[0] = Station{x: 0, p: 0}
	for i := 1; i <= m; i++ {
		fmt.Fscan(reader, &stations[i].x, &stations[i].p)
	}

	subStations := stations[1 : m+1]
	sort.Slice(subStations, func(i, j int) bool {
		return subStations[i].x < subStations[j].x
	})

	stations[m+1] = Station{x: d, p: 0}

	for i := 0; i <= m; i++ {
		if stations[i+1].x-stations[i].x > n {
			fmt.Println("-1")
			return
		}
	}

	nextCheaper := make([]int, m+2)
	stack := make([]int, 0, m+2)
	for i := 1; i <= m+1; i++ {
		for len(stack) > 0 && stations[stack[len(stack)-1]].p > stations[i].p {
			nextCheaper[stack[len(stack)-1]] = i
			stack = stack[:len(stack)-1]
		}
		stack = append(stack, i)
	}

	var ans int64 = 0
	currentFuel := n - stations[1].x
	for i := 1; i <= m; i++ {
		j := nextCheaper[i]
		var targetFuel int64
		if stations[j].x-stations[i].x <= n {
			targetFuel = stations[j].x - stations[i].x
		} else {
			targetFuel = n
		}

		if targetFuel > currentFuel {
			ans += (targetFuel - currentFuel) * stations[i].p
			currentFuel = targetFuel
		}
		currentFuel -= (stations[i+1].x - stations[i].x)
	}

	fmt.Println(ans)
}