結果
問題 | No.2438 Double Least Square |
ユーザー |
![]() |
提出日時 | 2023-08-11 23:42:30 |
言語 | Julia (2.11.2) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,717 bytes |
コンパイル時間 | 304 ms |
コンパイル使用メモリ | 5,376 KB |
実行使用メモリ | 481,472 KB |
最終ジャッジ日時 | 2024-10-01 17:29:05 |
合計ジャッジ時間 | 6,765 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 3 |
other | TLE * 1 -- * 29 |
ソースコード
using Printffunction solve(x::AbstractArray{Int}, y::AbstractArray{Int})if isempty(x)return 0, 0endcoef = sum(x .* y) / sum(x -> x^2, x)l = sum(x -> x^2, (y .- x .* coef))return coef, lendfunction main()N = parse(Int, readline())W, H = parse.(Int, split(readline()))x = zeros(Int, N)y = zeros(Int, N)for i in 1:Nx[i], y[i] = parse.(Int, split(readline()))end# (0, W)からの傾きでsortする.INF = 10^16slopes = zeros(Rational{Int}, N)for i in eachindex(x)if x[i] == 0slopes[i] = INFelseslopes[i] = (y[i] - (H // 2)) // x[i]endendslopes_perm = sortperm(slopes, rev=true)x_perm = sortperm(x)L_best = Infhu = -1hd = -1for i in eachindex(x)upper = slopes_perm[begin:i]lower = slopes_perm[i+1:end]for j in eachindex(x)left = Set(x_perm[begin:j])right = Set(x_perm[j+1:end])target_hu = (left ∩ upper) ∪ (right ∩ lower)target_hd = (left ∩ lower) ∪ (right ∩ upper)x_hu = getindex.(Ref(x), target_hu)y_hu = getindex.(Ref(y .- H), target_hu)coef_hu, l_hu = solve(x_hu, y_hu)x_hd = getindex.(Ref(x), target_hd)y_hd = getindex.(Ref(y), target_hd)coef_hd, l_hd = solve(x_hd, y_hd)L = l_hu + l_hdif L < L_bestL_best = Lhu = H + coef_hu * Whd = 0 + coef_hd * Wendendend@printf "%0.20f\n" L_bestendmain()