Cod sursa(job #3141463)

Utilizator TincaMateiTinca Matei TincaMatei Data 14 iulie 2023 03:47:28
Problema Secventa 3 Scor 100
Compilator rs Status done
Runda Arhiva de probleme Marime 5.34 kb
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 {}
    }
}