結果
問題 | No.8072 Sum of sqrt(x) |
ユーザー | Lisp_Coder |
提出日時 | 2024-04-05 02:18:16 |
言語 | Rust (1.77.0 + proconio) |
結果 |
OLE
|
実行時間 | - |
コード長 | 27,750 bytes |
コンパイル時間 | 26,142 ms |
コンパイル使用メモリ | 379,572 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-01 00:48:35 |
合計ジャッジ時間 | 24,516 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 2 ms
6,816 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 1 ms
6,816 KB |
testcase_04 | AC | 1 ms
6,816 KB |
testcase_05 | AC | 2 ms
6,820 KB |
testcase_06 | AC | 2 ms
6,816 KB |
testcase_07 | OLE | - |
testcase_08 | OLE | - |
testcase_09 | OLE | - |
testcase_10 | OLE | - |
testcase_11 | OLE | - |
testcase_12 | OLE | - |
testcase_13 | OLE | - |
testcase_14 | OLE | - |
testcase_15 | OLE | - |
testcase_16 | OLE | - |
testcase_17 | OLE | - |
testcase_18 | OLE | - |
testcase_19 | OLE | - |
testcase_20 | OLE | - |
testcase_21 | OLE | - |
testcase_22 | OLE | - |
testcase_23 | OLE | - |
testcase_24 | OLE | - |
testcase_25 | OLE | - |
testcase_26 | OLE | - |
testcase_27 | OLE | - |
testcase_28 | OLE | - |
testcase_29 | OLE | - |
ソースコード
#![recursion_limit = "2048"] #![allow(unused_variables)] #![allow(unused_assignments)] #![allow(unused_macros)] #![allow(non_snake_case)] #![allow(dead_code)] #![allow(unused_must_use)] #![allow(non_upper_case_globals)] #![allow(non_camel_case_types)] #![allow(unused_comparisons)] // crate import // use std::io::*; use std::cmp::*; // use std::collections::*; // use std::mem; // use std::ops::Bound::*; // use std::ops::RangeBounds; // use std::str::FromStr; // use std::fmt::Debug; // use std::fmt::Display; // use std::fmt::Write; // use std::fmt::Result; // use std::fmt::Formatter; // use std::fmt::Error; // use std::f32::consts::PI; // use std::f64::consts::PI; // 整数 1 つ読み込み (macro) macro_rules! read { ($($t:ty),*) => { { let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); let mut iter = input.split_whitespace(); ($(iter.next().unwrap().parse::<$t>().unwrap()),*) } }; } // 整数 1 つ読み込み (macro)(u128) macro_rules! read_u128 { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input.trim().parse::<u128>().unwrap() }}; } // 整数 1 つ読み込み (macro)(i128) macro_rules! read_i128 { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input.trim().parse::<i128>().unwrap() }}; } // 文字列 1 つ読み込み (macro) macro_rules! read_str { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input.trim().to_string() }}; } // 整数の 1 次元ベクトル読み込み (macro) macro_rules! read_vec { ($t:ty) => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input .trim() .split_whitespace() .map(|x| x.parse::<$t>().unwrap()) .collect::<Vec<$t>>() }}; } // 文字列の 1 次元ベクトル読み込み (macro) macro_rules! read_str_vec { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input .trim() .split_whitespace() .map(|x| x.to_string()) .collect::<Vec<String>>() }}; } // 整数の 2 次元ベクトル読み込み (macro) // 2 次元ベクトル読み込み (macro) macro_rules! read_2d_vec { ($t:ty, $rows:expr, $cols:expr) => {{ let mut v = Vec::with_capacity($rows); for _ in 0..$rows { v.push(read_vec!($t)); } v }}; } // char の 2 次元ベクトル読み込み (macro) macro_rules! read_2d_char_vec { ($rows:expr, $cols:expr) => {{ let mut v = Vec::with_capacity($rows); for _ in 0..$rows { v.push(read_char_vec!()); } v }}; } macro_rules! read_vecdeque { ($t:ty) => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); let mut iter = input.split_whitespace(); let mut vecdeque = VecDeque::new(); while let Some(token) = iter.next() { if let Ok(num) = token.parse::<$t>() { vecdeque.push_back(num); } else { eprintln!("Invalid number: {}", token); } } vecdeque }}; } // バイト列 1 つ読み込み (macro) macro_rules! read_bytes { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input.trim().as_bytes().to_vec() }}; } // chmin, chmax (macro) macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } // 文字の 1 次元ベクトル読み込み (macro) macro_rules! read_char_vec { () => {{ let mut input = String::new(); std::io::stdin().read_line(&mut input).ok(); input .trim() .chars() .map(|c| c.to_string()) .collect::<Vec<String>>() }}; } macro_rules! print_space_separated { ($coll:expr) => { println!( "{}", $coll .iter() .map(|&x| x.to_string()) .collect::<Vec<String>>() .join(" ") ); }; } macro_rules! print_space_separated_hashmap { ($map:expr) => { println!( "{}", $map.iter() .map(|(k, v)| format!("{} {}", k, v)) .collect::<Vec<String>>() .join(" ") ); }; } macro_rules! print_2d_vec { ($vec:expr) => { for v in $vec.iter() { println!( "{}", v.iter() .map(|&x| x.to_string()) .collect::<Vec<String>>() .join(" ") ); } }; } const MIN_USIZE: usize = std::usize::MIN; const MAX_USIZE: usize = std::usize::MAX; const MIN_ISIZE: isize = std::isize::MIN; const MAX_ISIZE: isize = std::isize::MAX; // macro gcd macro_rules! gcd { ($a:expr, $b:expr) => {{ let mut a = $a; let mut b = $b; while b > 0 { let tmp = b; b = a % b; a = tmp; } a }}; } // macro lcm macro_rules! lcm { ($a:expr, $b:expr) => {{ let a = $a; let b = $b; a / gcd!(a, b) * b }}; } // macro mod_pow macro_rules! mod_pow { ($a:expr, $b:expr, $m:expr) => {{ let mut a = $a; let mut b = $b; let m = $m; let mut ret = 1; while b > 0 { if b & 1 == 1 { ret = ret * a % m; } a = a * a % m; b >>= 1; } ret }}; } // macro mod_comb macro_rules! mod_comb { ($n:expr, $k:expr, $m:expr) => {{ let n = $n; let k = $k; let m = $m; let mut ret = 1; for i in 0..k { ret = ret * (n - i) % m; ret = ret * mod_pow!(i + 1, m - 2, m) % m; } ret }}; } // macro mod_fact macro_rules! mod_fact { ($n:expr, $m:expr) => {{ let n = $n; let m = $m; let mut ret = 1; for i in 1..n + 1 { ret = ret * i % m; } ret }}; } // macro mod_inv macro_rules! mod_inv { ($a:expr, $m:expr) => {{ let mut a = $a; let m = $m; let mut b = m; let mut u = 1; let mut v = 0; while b > 0 { let t = a / b; a -= t * b; std::mem::swap(&mut a, &mut b); u -= t * v; std::mem::swap(&mut u, &mut v); } u %= m; if u < 0 { u += m; } u }}; } // 縦に整数の読み込み(引数に型と個数) macro_rules! read_vec_vertical { ($t:ty, $n:expr) => {{ let mut v = Vec::with_capacity($n); for _ in 0..$n { v.push(read!($t)); } v }}; } // 縦に文字列の読み込み(引数に個数) macro_rules! read_str_vec_vertical { ($n:expr) => {{ let mut v = Vec::with_capacity($n); for _ in 0..$n { v.push(read_str!()); } v }}; } // 縦に byte 型の読み込み(引数に個数) macro_rules! read_bytes_vec_vertical { ($n:expr) => {{ let mut v = Vec::with_capacity($n); for _ in 0..$n { v.push(read_bytes!()); } v }}; } macro_rules! read_2d_str_vec { ($rows:expr) => {{ let mut v = Vec::with_capacity($rows); for _ in 0..$rows { v.push(read_str_vec!()); } v }}; } // 二分探索 (binary search) macro_rules! binary_search { ($arr:expr, $target:expr) => {{ let mut left = 0; let mut right = $arr.len(); while left < right { let mid = (left + right) / 2; if $arr[mid] < $target { left = mid + 1; } else { right = mid; } } left }}; } // 最長増加部分列 (LIS: Longest Increasing Subsequence) macro_rules! longest_increasing_subsequence { ($arr:expr) => {{ let mut lis_end: Vec<usize> = vec![0; $arr.len()]; let mut lis_len = 0; for &num in $arr { let index = binary_search!(&lis_end[..lis_len], num); lis_end[index] = num; if index == lis_len { lis_len += 1; } } lis_len }}; } // LCS(Longest Common Subsequence) macro_rules! longest_common_subsequence { ($s1:expr, $s2:expr) => {{ let n = $s1.len(); let m = $s2.len(); let mut dp = vec![vec![0; m + 1]; n + 1]; for i in 1..=n { for j in 1..=m { if $s1[i - 1] == $s2[j - 1] { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]); } } } let mut lcs_length = dp[n][m]; let mut lcs = Vec::with_capacity(lcs_length); let (mut i, mut j) = (n, m); while i > 0 && j > 0 { if $s1[i - 1] == $s2[j - 1] { lcs.push($s1[i - 1]); i -= 1; j -= 1; } else if dp[i - 1][j] > dp[i][j - 1] { i -= 1; } else { j -= 1; } } lcs.reverse(); (lcs_length, lcs) }}; } const MOD: usize = 1_000_000_007; const INF: isize = 2_000_000_000; pub type Graph = Vec<Vec<usize>>; #[cfg(target_pointer_width = "64")] pub type fsize = f64; #[cfg(target_pointer_width = "32")] pub type fsize = f32; pub fn lower_bound<T: Ord>(arr: &[T], x: &T) -> usize { let mut l = 0; let mut r = arr.len(); while l < r { let m = (l + r) / 2; if &arr[m] < x { l = m + 1; } else { r = m; } } l } pub fn upper_bound<T: Ord>(arr: &[T], x: &T) -> usize { let mut l = 0; let mut r = arr.len(); while l < r { let m = (l + r) / 2; if &arr[m] <= x { l = m + 1; } else { r = m; } } l } pub fn print_type_of<T>(_: T) { println!("{}", std::any::type_name::<T>()); } // 2 次元の char 型のベクタを出力する pub fn print_2d_char_vec(v: &Vec<Vec<char>>) { for i in 0..v.len() { for j in 0..v[i].len() { print!("{}", v[i][j]); } println!(); } } // vector の merge_sort 関数 pub fn merge_sort<T: Ord + Clone>(arr: &mut Vec<T>) { let n = arr.len(); if n <= 1 { return; } let mid = n / 2; let mut left = arr[..mid].to_vec(); let mut right = arr[mid..].to_vec(); merge_sort(&mut left); merge_sort(&mut right); let (mut i, mut j, mut k) = (0, 0, 0); while i < left.len() && j < right.len() { if left[i] < right[j] { arr[k] = left[i].clone(); i += 1; } else { arr[k] = right[j].clone(); j += 1; } k += 1; } while i < left.len() { arr[k] = left[i].clone(); i += 1; k += 1; } while j < right.len() { arr[k] = right[j].clone(); j += 1; k += 1; } } // vector の quick_sort 関数 pub fn quick_sort<T: Ord + Clone>(arr: &mut Vec<T>) { if arr.len() <= 1 { return; } let pivot = arr[0].clone(); let mut left = Vec::new(); let mut right = Vec::new(); for i in 1..arr.len() { if arr[i] < pivot { left.push(arr[i].clone()); } else { right.push(arr[i].clone()); } } quick_sort(&mut left); quick_sort(&mut right); let mut k = 0; for x in left { arr[k] = x; k += 1; } arr[k] = pivot; k += 1; for x in right { arr[k] = x; k += 1; } } // dfs macro_rules! dfs { ($graph:expr, $node:expr, $visited:expr, $action:block) => {{ let mut stack = vec![$node]; while let Some(node) = stack.pop() { if !$visited[node] { $visited[node] = true; $action for &next_node in &$graph[node] { if !$visited[next_node] { stack.push(next_node); } } } } }}; } // bfs macro_rules! bfs { ($graph:expr, $node:expr, $visited:expr, $action:block) => {{ let mut queue = VecDeque::new(); queue.push_back($node); while let Some(node) = queue.pop_front() { if !$visited[node] { $visited[node] = true; $action for &next_node in &$graph[node] { if !$visited[next_node] { queue.push_back(next_node); } } } } }}; } // dijkstra macro_rules! dijkstra { ($graph:expr, $start:expr) => {{ let mut dist = vec![std::usize::MAX; $graph.len()]; let mut heap = BinaryHeap::new(); dist[$start] = 0; heap.push(std::cmp::Reverse((0, $start))); while let Some(std::cmp::Reverse((cost, node))) = heap.pop() { if cost > dist[node] { continue; } for &(next_node, next_cost) in &$graph[node] { let next_cost = cost + next_cost; if next_cost < dist[next_node] { heap.push(std::cmp::Reverse((next_cost, next_node))); dist[next_node] = next_cost; } } } dist }}; } // ワーシャルフロイド法 macro_rules! warshall_floyd { ($graph:expr) => {{ let mut dist = $graph.clone(); let n = dist.len(); for k in 0..n { for i in 0..n { for j in 0..n { dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]); } } } dist }}; } // ベルマンフォード法 macro_rules! bellman_ford { ($graph:expr, $start:expr) => {{ let n = $graph.len(); let mut dist = vec![std::usize::MAX; n]; dist[$start] = 0; for _ in 0..n { for i in 0..n { for &(next_node, next_cost) in &$graph[i] { if dist[i] != std::usize::MAX && dist[next_node] > dist[i] + next_cost { dist[next_node] = dist[i] + next_cost; if i == n - 1 { return None; } } } } } Some(dist) }}; } // プリム法 macro_rules! prim { ($graph:expr) => {{ let n = $graph.len(); let mut used = vec![false; n]; let mut heap = BinaryHeap::new(); let mut cost = 0; heap.push((0, 0)); while let Some((c, v)) = heap.pop() { if used[v] { continue; } used[v] = true; cost += c; for &(to, c) in &$graph[v] { heap.push((c, to)); } } cost }}; } // クラスカル法 macro_rules! kruskal { ($graph:expr) => {{ let mut edges = vec![]; for (i, vec) in $graph.iter().enumerate() { for &(j, cost) in vec { edges.push((cost, i, j)); } } edges.sort(); let mut uf = UnionFind::new($graph.len()); let mut cost = 0; for &(c, a, b) in &edges { if !uf.same(a, b) { uf.unite(a, b); cost += c; } } cost }}; } // ユニオンファインド pub struct UnionFind { parent: Vec<usize>, rank: Vec<usize>, } impl UnionFind { pub fn new(n: usize) -> UnionFind { let mut parent = vec![0; n]; for i in 0..n { parent[i] = i; } UnionFind { parent: parent, rank: vec![0; n], } } pub fn root(&mut self, x: usize) -> usize { if self.parent[x] == x { x } else { let parent = self.parent[x]; let root = self.root(parent); self.parent[x] = root; root } } pub fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } pub fn unite(&mut self, x: usize, y: usize) { let x = self.root(x); let y = self.root(y); if x == y { return; } if self.rank[x] < self.rank[y] { self.parent[x] = y; } else { self.parent[y] = x; if self.rank[x] == self.rank[y] { self.rank[x] += 1; } } } } // 二部グラフ判定 macro_rules! is_bipartite_graph { ($graph:expr) => {{ let n = $graph.len(); let mut color = vec![0; n]; let mut stack = Vec::new(); for i in 0..n { if color[i] != 0 { continue; } stack.push(i); color[i] = 1; while let Some(node) = stack.pop() { for &next_node in &$graph[node] { if color[next_node] == 0 { color[next_node] = -color[node]; stack.push(next_node); } else if color[next_node] == color[node] { return false; } } } } true }}; } // トポロジカルソート macro_rules! topological_sort { ($graph:expr) => {{ let n = $graph.len(); let mut indeg = vec![0; n]; for vec in &$graph { for &to in vec { indeg[to] += 1; } } let mut stack = Vec::new(); for i in 0..n { if indeg[i] == 0 { stack.push(i); } } let mut res = Vec::new(); while let Some(node) = stack.pop() { res.push(node); for &next_node in &$graph[node] { indeg[next_node] -= 1; if indeg[next_node] == 0 { stack.push(next_node); } } } res }}; } // 二部マッチング macro_rules! bipartite_matching { ($graph:expr) => {{ let n = $graph.len(); let m = $graph[0].len(); let mut match_to = vec![None; m]; let mut res = 0; for i in 0..n { let mut visited = vec![false; n]; if dfs_bipartite_matching!($graph, i, &mut visited, &mut match_to) { res += 1; } } res }}; } // 高速フーリエ変換 // fft macro_rules! convolution_macro { ($a:expr, $b:expr) => {{ let mut a = $a; let mut b = $b; let m: i64 = 998244353; let mut n = 1; let na = a.len(); let nb = b.len(); while 2 * n < na + nb - 1 { n *= 2; } n *= 2; let mut p3 = vec![1_i64; 23]; // p3[i] = rn^(2^i) (1,rn,rn^2,rn^4,...,rn^(2^22)) let mut invp3 = vec![1_i64; 23]; // invp3[i] = p3[i]の逆元 let rn = pow_mod_macro!(3, (m - 1) / n as i64, m); p3[1] = rn; for i in 2..23 { p3[i] = p3[i - 1] * p3[i - 1] % m; } for i in 1..23 { invp3[i] = pow_mod_macro!(p3[i], m - 2, m); } for i in na..n { a.push(0); } for i in nb..n { b.push(0); } let a_fft = ntt_macro!(n, &a, &p3, 1); let b_fft = ntt_macro!(n, &b, &p3, 1); let mut c_fft = vec![0; n]; for i in 0..n { c_fft[i] = a_fft[i] * b_fft[i] % m; } let mut c = ntt_macro!(n, &c_fft, &invp3, 1); for i in 0..n { c[i] = c[i] * pow_mod_macro!(n as i64, m - 2, m) % m; } c }}; } macro_rules! ntt_macro { ($n:expr, $v:expr, $root:expr, $depth:expr) => {{ let m = 998244353; if $n == 1 { $v.to_vec() } else { let mut even = vec![]; let mut odd = vec![]; for i in 0..$n { if i % 2 == 0 { even.push($v[i]); } else { odd.push($v[i]); } } let fft_even = ntt_macro!($n / 2, &even, &$root, $depth + 1); let fft_odd = ntt_macro!($n / 2, &odd, &$root, $depth + 1); let mut now = 1; let mut b = vec![0; $n]; for i in 0..$n { if i < $n / 2 { b[i] = (fft_even[i] + now * fft_odd[i] % m) % m; now = now * $root[$depth] % m; } else { b[i] = (fft_even[i - $n / 2] + now * fft_odd[i - $n / 2] % m) % m; now = now * $root[$depth] % m; } } b } }}; } macro_rules! pow_mod_macro { ($a:expr, $b:expr, $m:expr) => {{ let mut a = $a; let mut b = $b; let mut res: i64 = 1; while b > 0 { if b & 1 == 1 { res = res * a % $m; } a = a * a % $m; b >>= 1; } res }}; } // Z algorithm macro_rules! z_algorithm { ($s:expr) => {{ let bytes = $s.as_bytes(); let length = bytes.len(); let mut z = vec![0; length]; z[0] = length; let mut l = 0; let mut r = 0; for i in 1..length { if i > r { l = i; r = i; while r < length && bytes[r - l] == bytes[r] { r += 1; } z[i] = r - l; r -= 1; } else { let k = i - l; if z[k] < r - i + 1 { z[i] = z[k]; } else { l = i; while r < length && bytes[r - l] == bytes[r] { r += 1; } z[i] = r - l; r -= 1; } } } z }}; } // fenwick tree (usize) pub struct FenwickTree { n: usize, data: Vec<usize>, } impl FenwickTree { pub fn new(n: usize) -> FenwickTree { FenwickTree { n: n, data: vec![0; n + 1], } } pub fn add(&mut self, i: usize, x: usize) { let mut i = i as i32; while i <= self.n as i32 { self.data[i as usize] += x; i += i & -i; } } pub fn sum(&self, i: usize) -> usize { let mut i = i as i32; let mut res = 0; while i > 0 { res += self.data[i as usize]; i -= i & -i; } res } } // DSU (Disjoint Set Union) pub struct DSU { parent: Vec<usize>, rank: Vec<usize>, } impl DSU { pub fn new(n: usize) -> DSU { let mut parent = vec![0; n]; for i in 0..n { parent[i] = i; } DSU { parent: parent, rank: vec![0; n], } } pub fn root(&mut self, x: usize) -> usize { if self.parent[x] == x { x } else { let parent = self.parent[x]; let root = self.root(parent); self.parent[x] = root; root } } pub fn same(&mut self, x: usize, y: usize) -> bool { self.root(x) == self.root(y) } pub fn unite(&mut self, x: usize, y: usize) { let x = self.root(x); let y = self.root(y); if x == y { return; } if self.rank[x] < self.rank[y] { self.parent[x] = y; } else { self.parent[y] = x; if self.rank[x] == self.rank[y] { self.rank[x] += 1; } } } } fn power(a: i64, b: i64, modulo: i64) -> i64 { let mut power = a; let mut remain = 1_i64; for i in 0..30 { if b & (1_i64 << i) > 0 { remain *= power; remain %= modulo; } power *= power % modulo; power %= modulo; } remain } fn factorial(a: i64, modulo: i64) -> i64 { let mut remain: i64 = 1_i64; for i in 2..=a { remain *= i % modulo; remain %= modulo; } remain } // 最大マッチング fn maximum_matching(graph: &Vec<Vec<usize>>) -> usize { let n = graph.len(); let mut match_to = vec![None; n]; // マッチング先を格納する配列 let mut res = 0; for i in 0..n { let mut visited = vec![false; n]; if dfs_maximum_matching(graph, i, &mut visited, &mut match_to) { res += 1; } } res } fn dfs_maximum_matching(graph: &Vec<Vec<usize>>, node: usize, visited: &mut Vec<bool>, match_to: &mut Vec<Option<usize>>) -> bool { if visited[node] { return false; } visited[node] = true; for &next_node in &graph[node] { if match_to[next_node].is_none() || dfs_maximum_matching(graph, match_to[next_node].unwrap(), visited, match_to) { match_to[next_node] = Some(node); return true; } } false } // 最大マッチング fn maximum_matching_bipartite(graph: &Vec<Vec<usize>>) -> usize { let n = graph.len(); let m = graph[0].len(); let mut match_to = vec![None; m]; // マッチング先を格納する配列 let mut res = 0; for i in 0..n { let mut visited = vec![false; n]; if dfs_maximum_matching_bipartite(graph, i, &mut visited, &mut match_to) { res += 1; } } res } fn dfs_maximum_matching_bipartite(graph: &Vec<Vec<usize>>, node: usize, visited: &mut Vec<bool>, match_to: &mut Vec<Option<usize>>) -> bool { if visited[node] { return false; } visited[node] = true; for &next_node in &graph[node] { if match_to[next_node].is_none() || dfs_maximum_matching_bipartite(graph, match_to[next_node].unwrap(), visited, match_to) { match_to[next_node] = Some(node); return true; } } false } fn sqrt(n: isize) -> fsize { (n as f64).sqrt() } // k行めに\sum_{i=1}^{k} \sqrt{x_i}を出力する fn main() { let n = read!(isize); let mut sum = 0.0; for i in 0..n { let x = read!(isize); sum += sqrt(x); println!("{:.30}", sum); } }