For problem statement at 0-999/700-799/730-739/730/problemI.txt this is a correct solution, but verifier at 0-999/700-799/730-739/730/verifierI.go ends with case 1 failed: expected 34
1
2 3 got 34
1
3 2
input:
3 1 2
19 8 10
6 8 7
exit status 1 can you fix the verifier? package main
import (
"bufio"
"container/heap"
"fmt"
"os"
"sort"
)
type Student struct {
id int
a int
b int
d int
}
type Item struct {
val int
id int
}
type MinHeap []Item
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool {
if h[i].val == h[j].val {
return h[i].id < h[j].id
}
return h[i].val < h[j].val
}
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
*h = append(*h, x.(Item))
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
const NEG int64 = -1 << 60
func main() {
in := bufio.NewReaderSize(os.Stdin, 1<<20)
out := bufio.NewWriterSize(os.Stdout, 1<<20)
defer out.Flush()
var n, p, s int
fmt.Fscan(in, &n, &p, &s)
a := make([]int, n)
b := make([]int, n)
for i := 0; i < n; i++ {
fmt.Fscan(in, &a[i])
}
for i := 0; i < n; i++ {
fmt.Fscan(in, &b[i])
}
students := make([]Student, n)
for i := 0; i < n; i++ {
students[i] = Student{
id: i + 1,
a: a[i],
b: b[i],
d: a[i] - b[i],
}
}
sort.Slice(students, func(i, j int) bool {
if students[i].d == students[j].d {
return students[i].id < students[j].id
}
return students[i].d > students[j].d
})
pref := make([]int64, n+1)
for i := 0; i <= n; i++ {
pref[i] = NEG
}
if p == 0 {
for i := 0; i <= n; i++ {
pref[i] = 0
}
} else {
h := &MinHeap{}
heap.Init(h)
var sum int64
for i := 1; i <= n; i++ {
st := students[i-1]
heap.Push(h, Item{val: st.a, id: st.id})
sum += int64(st.a)
if h.Len() > p {
x := heap.Pop(h).(Item)
sum -= int64(x.val)
}
if h.Len() == p {
pref[i] = sum
}
}
}
suf := make([]int64, n+2)
for i := 0; i <= n+1; i++ {
suf[i] = NEG
}
if s == 0 {
for i := 1; i <= n+1; i++ {
suf[i] = 0
}
} else {
h := &MinHeap{}
heap.Init(h)
var sum int64
for i := n; i >= 1; i-- {
st := students[i-1]
heap.Push(h, Item{val: st.b, id: st.id})
sum += int64(st.b)
if h.Len() > s {
x := heap.Pop(h).(Item)
sum -= int64(x.val)
}
if h.Len() == s {
suf[i] = sum
}
}
}
best := NEG
bestK := 0
for k := 0; k <= n; k++ {
if pref[k] == NEG || suf[k+1] == NEG {
continue
}
cur := pref[k] + suf[k+1]
if cur > best {
best = cur
bestK = k
}
}
prog := make([]int, 0, p)
if p > 0 {
h := &MinHeap{}
heap.Init(h)
for i := 1; i <= bestK; i++ {
st := students[i-1]
heap.Push(h, Item{val: st.a, id: st.id})
if h.Len() > p {
heap.Pop(h)
}
}
for h.Len() > 0 {
x := heap.Pop(h).(Item)
prog = append(prog, x.id)
}
}
sport := make([]int, 0, s)
if s > 0 {
h := &MinHeap{}
heap.Init(h)
for i := bestK + 1; i <= n; i++ {
st := students[i-1]
heap.Push(h, Item{val: st.b, id: st.id})
if h.Len() > s {
heap.Pop(h)
}
}
for h.Len() > 0 {
x := heap.Pop(h).(Item)
sport = append(sport, x.id)
}
}
fmt.Fprintln(out, best)
for i, id := range prog {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, id)
}
fmt.Fprintln(out)
for i, id := range sport {
if i > 0 {
fmt.Fprint(out, " ")
}
fmt.Fprint(out, id)
}
fmt.Fprintln(out)
}