Skip to main content

min_plus_convolution_convex_merge

competitive::math

Function min_plus_convolution_convex_merge 

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

Computes convolution of two convex inputs by merging their slope sequences.

The running time is O(n + m).

ยงPanics

Panics unless both inputs are finite and convex.

Examples found in repository?
crates/library_checker/src/convolution/min_plus_convolution_convex_convex.rs (line 8)
5pub fn min_plus_convolution_convex_convex(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_merge(&a, &b));
9}