← Home
For problem statement at 0-999/700-799/730-739/739/problemE.txt this is a correct solution, but verifier at 0-999/700-799/730-739/739/verifierE.go ends with Test 1 failed
Input:
1 0 1
0.743995
0.454237
Expected: 0.454237 Got: 0.454240

exit status 1 can you fix the verifier? package main

import (
	"fmt"
)

func main() {
	var n, a, b int
	fmt.Scan(&n, &a, &b)

	p := make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&p[i])
	}
	u := make([]float64, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&u[i])
	}

	if a > n {
		a = n
	}
	if b > n {
		b = n
	}

	low := 0.0
	high := 1.0
	var lambda float64

	dp := make([]float64, a+1)
	cnt := make([]int, a+1)

	for step := 0; step < 65; step++ {
		lambda = (low + high) / 2.0

		for j := 1; j <= a; j++ {
			dp[j] = -1e9
		}
		dp[0] = 0
		cnt[0] = 0

		for i := 0; i < n; i++ {
			pi := p[i]
			ui := u[i]
			pui := pi + ui - pi*ui - lambda
			ui_lambda := ui - lambda

			for j := a; j >= 0; j-- {
				best_val := dp[j]
				best_cnt := cnt[j]

				v1 := dp[j] + ui_lambda
				if v1 > best_val+1e-11 {
					best_val = v1
					best_cnt = cnt[j] + 1
				} else if v1 > best_val-1e-11 && cnt[j]+1 > best_cnt {
					best_val = v1
					best_cnt = cnt[j] + 1
				}

				if j > 0 {
					v2 := dp[j-1] + pi
					if v2 > best_val+1e-11 {
						best_val = v2
						best_cnt = cnt[j-1]
					} else if v2 > best_val-1e-11 && cnt[j-1] > best_cnt {
						best_val = v2
						best_cnt = cnt[j-1]
					}

					v3 := dp[j-1] + pui
					if v3 > best_val+1e-11 {
						best_val = v3
						best_cnt = cnt[j-1] + 1
					} else if v3 > best_val-1e-11 && cnt[j-1]+1 > best_cnt {
						best_val = v3
						best_cnt = cnt[j-1] + 1
					}
				}
				dp[j] = best_val
				cnt[j] = best_cnt
			}
		}

		if cnt[a] < b {
			high = lambda
		} else {
			low = lambda
		}
	}

	fmt.Printf("%.5f\n", dp[a]+lambda*float64(b))
}