trang chủ / đề bài / icpc22_mn_e

Tổng bình phương

Đề bài

Mô tả

Anh Nhật có một bài toán gồm N bước. Ở bước thứ i, anh được cho hai số Ai và Bi, rồi phải chọn một số thực Ri sao cho Ri không lớn hơn các số đã chọn ở những bước trước đó (tức là R1≥R2≥…≥RN). Điểm của bài toán được định nghĩa là

∑i=1N(Ai−Ri·Bi)2

Hỏi điểm nhỏ nhất mà anh Nhật có thể đạt được là bao nhiêu?

Dữ liệu vào

  • Dòng đầu tiên chứa số nguyên N (2≤N≤5×105).
  • Dòng thứ hai chứa N số nguyên A1,A2,…,AN.
  • Dòng thứ ba chứa N số nguyên B1,B2,…,BN.

Dữ liệu ra

In ra điểm nhỏ nhất anh Nhật có thể đạt được. Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối không vượt quá 10−6.

Ràng buộc

  • 2≤N≤5×105
  • 1≤Ai,Bi≤1000

Ví dụ

Input Output Giải thích
2
2 5
1 8
0.000000000000000 Chọn R1=2, R2=0.625: cả hai số hạng đều bằng 0 và R1≥R2.
5
7 9 1 4 3
9 8 6 13 1
12.247238031469687
10
66 23 51 81 60 7 26 127 66 8
9 88 77 12 2 38 7 63 90 111
17698.696831405897683

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0