blog.bouzuya.net

2023-07-24 ABC189 C を解いた

// O(N)
use proconio::input;

fn main() {
    input! {
        n: usize,
        mut a: [usize; n],
    };
    a.push(0);
    let mut max = 0_usize;
    let mut stack: Vec<(usize, usize)> = vec![];
    for (i, a_i) in a.iter().copied().enumerate() {
        let mut left_index = i;
        while let Some((l, a_l)) = stack.pop() {
            match a_l.cmp(&a_i) {
                std::cmp::Ordering::Less => {
                    stack.push((l, a_l));
                    break;
                }
                std::cmp::Ordering::Equal => {
                    left_index = l;
                    max = max.max(a_l * (i - left_index));
                }
                std::cmp::Ordering::Greater => {
                    left_index = l;
                    max = max.max(a_l * (i - left_index));
                }
            }
        }
        stack.push((left_index, a_i));
    }
    let ans = max;
    println!("{}", ans);
}
// O(N^2)
use proconio::input;

fn main() {
    input! {
        n: usize,
        a: [usize; n],
    };
    let mut ans = 0_usize;
    for l in 0..n {
        let mut max = a[l];
        for r in l..n {
            max = max.min(a[r]);
            ans = ans.max(max * (r - l + 1));
        }
    }
    println!("{}", ans);
}

今日のコミット。