← Home
For problem statement at 1000-1999/1200-1299/1200-1209/1203/problemF2.txt this is a correct solution, but verifier at 1000-1999/1200-1299/1200-1209/1203/verifierF2.go ends with All tests passed can you fix the verifier? package main

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

type Project struct {
	a int
	b int
}

type FastScanner struct {
	r *bufio.Reader
}

func NewFastScanner() *FastScanner {
	return &FastScanner{r: bufio.NewReaderSize(os.Stdin, 1<<20)}
}

func (fs *FastScanner) NextInt() int {
	sign, val := 1, 0
	c, _ := fs.r.ReadByte()
	for (c < '0' || c > '9') && c != '-' {
		c, _ = fs.r.ReadByte()
	}
	if c == '-' {
		sign = -1
		c, _ = fs.r.ReadByte()
	}
	for c >= '0' && c <= '9' {
		val = val*10 + int(c-'0')
		c, _ = fs.r.ReadByte()
	}
	fs.r.UnreadByte()
	return sign * val
}

func main() {
	in := NewFastScanner()
	out := bufio.NewWriterSize(os.Stdout, 1<<20)
	defer out.Flush()

	n := in.NextInt()
	r := in.NextInt()

	pos := make([]Project, 0)
	neg := make([]Project, 0)

	for i := 0; i < n; i++ {
		a := in.NextInt()
		b := in.NextInt()
		if b >= 0 {
			pos = append(pos, Project{a, b})
		} else {
			neg = append(neg, Project{a, b})
		}
	}

	sort.Slice(pos, func(i, j int) bool {
		if pos[i].a == pos[j].a {
			return pos[i].b > pos[j].b
		}
		return pos[i].a < pos[j].a
	})

	donePos := 0
	for _, p := range pos {
		if r >= p.a {
			r += p.b
			donePos++
		} else {
			break
		}
	}

	sort.Slice(neg, func(i, j int) bool {
		si := neg[i].a + neg[i].b
		sj := neg[j].a + neg[j].b
		if si == sj {
			return neg[i].a > neg[j].a
		}
		return si > sj
	})

	dp := make([]int, len(neg)+1)
	for i := range dp {
		dp[i] = -1
	}
	dp[0] = r

	best := 0
	for _, p := range neg {
		for j := best; j >= 0; j-- {
			if dp[j] >= p.a {
				nr := dp[j] + p.b
				if nr >= 0 && nr > dp[j+1] {
					dp[j+1] = nr
					if j+1 > best {
						best = j + 1
					}
				}
			}
		}
	}

	ansNeg := 0
	for i := 0; i <= len(neg); i++ {
		if dp[i] >= 0 && i > ansNeg {
			ansNeg = i
		}
	}

	fmt.Fprintln(out, donePos+ansNeg)
}