Skip to main content

min_plus_convolution_convex_smawk

competitive::math

Function min_plus_convolution_convex_smawk 

Source 
pub fn min_plus_convolution_convex_smawk<T>(a: &[T], b: &[T]) -> Vec<T>
where
    T: Signed,
Expand description

Computes convolution when one input is convex using SMAWK in O(n + m).

ยงPanics

Panics unless both inputs are finite and at least one is convex.

Examples found in repository?
crates/library_checker/src/convolution/min_plus_convolution_convex_arbitrary.rs (line 8)
5pub fn min_plus_convolution_convex_arbitrary(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, a: [i64; n], b: [i64; m]);
8    pp!(@it min_plus_convolution_convex_smawk(&a, &b));
9}