Pagini recente » Cod sursa (job #1136667) | Cod sursa (job #541177) | Cod sursa (job #3220059) | Cod sursa (job #972196) | Cod sursa (job #3141463)
pub use __cargo_equip::prelude::*;
use dopecomp_io::{InParser, OutParser};
use std::collections::VecDeque;
use std::io::{BufReader, BufWriter, Read, Write};
// Solve the task with the given input and print it to the given output.
fn solve_test<I: Read, O: Write>(fin: &mut InParser<I>, fout: &mut OutParser<O>) {
let (n, l, r): (usize, usize, usize) = (fin.read(), fin.read(), fin.read());
let mut c = vec![0; 1 + n];
let mut t = vec![0; 1 + n];
for i in 1..=n {
c[i] = fin.read();
}
for i in 1..=n {
t[i] = fin.read();
}
let check = |mid: f64| {
let mut sp: Vec<f64> = vec![0.0; 1 + n];
let mut dq = VecDeque::<usize>::new();
for i in 1..=n {
sp[i] = sp[i - 1] + (c[i] as f64) - mid * (t[i] as f64);
if i >= l {
while !dq.is_empty() && sp[i - l] < sp[*dq.back().unwrap()] {
dq.pop_back();
}
dq.push_back(i - l);
}
match dq.front() {
Some(t) => {
if sp[*t] < sp[i] {
return true;
}
}
_ => {}
};
if i >= r && dq.front() == Some(&(i - r)) {
dq.pop_front();
}
}
return false;
};
let mut l: f64 = 0.0;
let mut r: f64 = 1000.0;
for _ in 0..100 {
let mid = (l + r) / 2.0;
if check(mid) {
l = mid;
} else {
r = mid;
}
}
fout.write(format!("{:.2}", l));
}
// Run a sample with the given input and check with the correct output.
fn try_sample(input: &[u8], ok: &str) {
use std::io::Cursor;
let mut output = Vec::<u8>::new();
solve_test(
&mut InParser::new(BufReader::new(Cursor::new(input))),
&mut OutParser::new(BufWriter::new(&mut output)),
);
assert_eq!(std::str::from_utf8(&output).unwrap(), ok);
}
// Run the first sample of the problem.
fn sample_1() {
try_sample(
br#"5 1 2
1 1 3 2 5
4 2 5 3 6"#,
r#"0.83"#,
);
}
fn main() {
sample_1();
solve_test(
&mut InParser::from_filename("secv3.in"),
&mut OutParser::from_filename("secv3.out"),
);
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `dopecomp_io 0.1.0 (git+https://github.com/tincaMatei/competitive-rust#7eb8b8cb339c6c64f448b287858932e15a77862d)` licensed under **missing** as `crate::__cargo_equip::crates::dopecomp_io`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod dopecomp_io {#![allow(dead_code)]use std::io::{Read,BufRead,Stdin,BufReader,Write,BufWriter,Stdout};use std::fs::File;use std::str::FromStr;use std::fmt::Debug;pub struct InParser<T:Read>{reader:BufReader<T>,buffer:Vec<u8>,cursor:usize,eof_flag:bool,}impl InParser<Stdin>{pub fn from_stdin()->InParser<Stdin>{InParser::new(std::io::stdin())}}impl InParser<File>{pub fn from_filename(name:&str)->InParser<File>{InParser::new(File::open(name).expect("Failed to open file"))}}impl<T:Read>InParser<T>{pub fn new(reader:T)->InParser<T>{let mut reader=BufReader::new(reader);let buffer=reader.fill_buf().expect("Failed to fill buffer").to_vec();InParser{reader,buffer,cursor:0,eof_flag:false,}}pub fn get_current_byte(&mut self)->u8{if self.cursor<self.buffer.len(){return self.buffer[self.cursor];}panic!("Outside of buffer")}pub fn advance_cursor(&mut self){self.cursor+=1;if self.cursor>=self.buffer.len(){self.reader.consume(self.buffer.len());self.buffer=self.reader.fill_buf().expect("Failed to fill buffer").to_vec();self.eof_flag=self.buffer.is_empty();self.cursor=0;}}fn skip_spaces(&mut self){while!self.eof_flag&&(self.get_current_byte()==b' '||self.get_current_byte()==b'\n'){self.advance_cursor();}}fn get_token(&mut self)->Vec<u8>{let mut token_buf:Vec<u8> =Vec::new();self.skip_spaces();while!self.eof_flag&&self.get_current_byte()!=b' '&&self.get_current_byte()!=b'\n'{let byte=self.get_current_byte();token_buf.push(byte);self.advance_cursor();}token_buf}pub fn read_string(&mut self)->String{let token=self.get_token();let strval=std::str::from_utf8(&token).expect("Failed to convert into valid utf8").trim();strval.to_string()}pub fn read_number<F:From<i64>>(&mut self)->F{self.skip_spaces();let sgn=if self.get_current_byte()==b'-'{self.advance_cursor();-1}else{1};let mut nr=0;while!self.eof_flag&&self.get_current_byte().is_ascii_digit(){nr=nr*10+(self.get_current_byte()-b'0')as i64;self.advance_cursor();}F::from(nr*sgn)}pub fn read<F>(&mut self)->F where F:FromStr,<F as FromStr>::Err:Debug{self.read_string().parse::<F>().unwrap()}}pub struct OutParser<T:Write>{writer:BufWriter<T>,}impl<T:Write>OutParser<T>{pub fn new(writer:T)->OutParser<T>{OutParser{writer:BufWriter::new(writer)}}pub fn write<F:ToString>(&mut self,val:F)->&mut Self{self.writer.write(&val.to_string().as_bytes()).expect("Failed to write");self}}impl OutParser<Stdout>{pub fn from_stdout()->OutParser<Stdout>{OutParser::new(std::io::stdout())}}impl OutParser<File>{pub fn from_filename(name:&str)->OutParser<File>{OutParser::new(File::create(name).expect("Failed to open file"))}}}
}
pub(crate) mod macros {
pub mod dopecomp_io {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod dopecomp_io {}
}
}