Educational Codeforces Round 121 (Rated for Div. 2) E. Black and White Tree

問題

https://codeforces.com/contest/1626/problem/E

木があります。いくつかの頂点が黒く塗られています。黒い頂点は必ず2つ以上あります。ある頂点に駒があるとき、黒い頂点を1つ選択することで、駒を選択した頂点の方向に1回動かすことができます。2回連続で同じ頂点を選択することができない時、頂点iに置かれた駒を適切に黒い頂点を選択することでいずれかの黒い頂点まで移動させることができるか求めてください。

解法

駒が置かれた頂点から見て同じ方向に2つ黒い頂点があるとき、これらを交互に選択することでその方向に連続で移動することができる。このことから、黒い頂点に移動できない頂点たちは、黒い頂点に囲まれた領域にあり、かつ、その領域の外に黒い頂点はない。

f:id:kenkoooo:20220121023933p:plain

コード

use std::collections::{BTreeSet, VecDeque};
use std::time::Instant;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let color: Vec<i64> = sc.vec(n);
    let mut graph = vec![vec![]; n];
    for _ in 1..n {
        let u = sc.usize0();
        let v = sc.usize0();
        graph[u].push(v);
        graph[v].push(u);
    }

    let a = (0..n).find(|&i| color[i] == 1).unwrap();
    let dist_a = bfs(&graph, a);
    let b = (0..n)
        .filter(|&i| i != a && color[i] == 1)
        .min_by_key(|&i| dist_a[i])
        .unwrap();
    let dist_b = bfs(&graph, b);
    let ab = dist_b[a];

    let ans = if let Some(x) = (0..n).find(|&i| dist_b[i] + dist_a[i] == ab && color[i] == 0) {
        let mut q = VecDeque::new();
        q.push_back(x);
        let n = graph.len();
        let mut dist = vec![n; n];
        dist[x] = 0;
        while let Some(v) = q.pop_front() {
            if color[v] == 1 {
                continue;
            }
            for &next in graph[v].iter() {
                if dist[next] > dist[v] + 1 {
                    dist[next] = dist[v] + 1;
                    q.push_back(next);
                }
            }
        }

        let reached = (0..n).filter(|&i| color[i] == 1 && dist[i] < n).count();
        let total = (0..n).filter(|&i| color[i] == 1).count();
        if reached != total {
            vec![1; n]
        } else {
            let mut ans = vec![1; n];
            for i in 0..n {
                if dist[i] < n {
                    ans[i] = 0;
                }
            }

            for i in 0..n {
                if graph[i].iter().any(|&i| color[i] == 1) {
                    ans[i] = 1;
                }
                if color[i] == 1 {
                    ans[i] = 1;
                }
            }

            let mut s = vec![BTreeSet::new(); n];
            for i in 0..n {
                for &j in graph[i].iter() {
                    if dist[i] < n && dist[j] < n {
                        s[i].insert(j);
                    }
                }
            }

            let mut q = VecDeque::new();
            for i in 0..n {
                if s[i].len() == 1 && color[i] == 0 {
                    q.push_back(i);
                }
            }
            while let Some(i) = q.pop_front() {
                let next = s[i].clone();
                for next in next {
                    assert!(s[next].remove(&i));
                    if s[next].len() == 1 && color[next] == 0 {
                        q.push_back(next);
                    }
                }
                s[i].clear();
            }

            for v in 0..n {
                if graph[v].iter().all(|&i| color[i] == 0) {
                    continue;
                }

                for &next in graph[v].iter() {
                    if s[next].is_empty() {
                        dfs(next, v, &graph, &mut ans);
                    }
                }
            }

            if (0..n)
                .filter(|&i| s[i].len() >= 3)
                .any(|v| graph[v].iter().any(|&next| color[next] == 1))
            {
                vec![1; n]
            } else {
                ans
            }
        }
    } else {
        assert_eq!(ab, 1);
        vec![1; n]
    };

    for (i, ans) in ans.into_iter().enumerate() {
        if i > 0 {
            sc.write(' ');
        }
        sc.write(ans);
    }
    sc.write('\n');
}
fn dfs(v: usize, p: usize, graph: &Vec<Vec<usize>>, ans: &mut Vec<i64>) {
    ans[v] = 1;
    for &next in graph[v].iter() {
        if p == next {
            continue;
        }
        dfs(next, v, graph, ans);
    }
}

fn bfs(graph: &Vec<Vec<usize>>, from: usize) -> Vec<usize> {
    let mut q = VecDeque::new();
    q.push_back(from);
    let n = graph.len();
    let mut dist = vec![n; n];
    dist[from] = 0;
    while let Some(v) = q.pop_front() {
        for &next in graph[v].iter() {
            if dist[next] > dist[v] + 1 {
                dist[next] = dist[v] + 1;
                q.push_back(next);
            }
        }
    }
    dist
}

pub struct ReRooting<T, Identity, Merge, AddRoot> {
    dp: Vec<Vec<T>>,
    ans: Vec<T>,
    graph: Vec<Vec<usize>>,
    identity: Identity,
    merge: Merge,
    add_root: AddRoot,
}

impl<T, Identity, Merge, AddRoot> ReRooting<T, Identity, Merge, AddRoot>
where
    T: Clone,
    Identity: Fn() -> T,
    Merge: Fn(T, T) -> T,
    AddRoot: Fn(T) -> T,
{
    pub fn new(n: usize, identity: Identity, merge: Merge, add_root: AddRoot) -> Self {
        Self {
            dp: vec![vec![]; n],
            ans: vec![identity(); n],
            graph: vec![vec![]; n],
            identity,
            merge,
            add_root,
        }
    }
    pub fn add_edge(&mut self, a: usize, b: usize) {
        self.graph[a].push(b);
    }
    pub fn build(&mut self) {
        self.dfs(0, 0);
        self.dfs2(0, 0, (self.identity)());
    }

    fn dfs(&mut self, v: usize, p: usize) -> T {
        let mut sum = (self.identity)();
        let deg = self.graph[v].len();
        self.dp[v] = vec![(self.identity)(); deg];
        let next = self.graph[v].clone();
        for (i, next) in next.into_iter().enumerate() {
            if next == p {
                continue;
            }
            let t = self.dfs(next, v);
            self.dp[v][i] = t.clone();
            sum = (self.merge)(sum, t);
        }
        (self.add_root)(sum)
    }
    fn dfs2(&mut self, v: usize, p: usize, dp_p: T) {
        for (i, &next) in self.graph[v].iter().enumerate() {
            if next == p {
                self.dp[v][i] = dp_p.clone();
            }
        }

        let deg = self.graph[v].len();
        let mut dp_l = vec![(self.identity)(); deg + 1];
        let mut dp_r = vec![(self.identity)(); deg + 1];
        for i in 0..deg {
            dp_l[i + 1] = (self.merge)(dp_l[i].clone(), self.dp[v][i].clone());
        }
        for i in (0..deg).rev() {
            dp_r[i] = (self.merge)(dp_r[i + 1].clone(), self.dp[v][i].clone());
        }

        self.ans[v] = (self.add_root)(dp_l[deg].clone());

        let next = self.graph[v].clone();
        for (i, next) in next.into_iter().enumerate() {
            if next == p {
                continue;
            }
            self.dfs2(
                next,
                v,
                (self.add_root)((self.merge)(dp_l[i].clone(), dp_r[i + 1].clone())),
            );
        }
    }
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ABC233 G - Strongest Takahashi

atcoder.jp

空行はスキップして良いという発想も大事だが、そもそも全ての長方形領域を列挙した O(N4) もそこまで大きくないというのに気付かなかった。

|rust| const INF: i64 = 1 << 60; fn main() { let (r, w) = (std::io::stdin(), std::io::stdout()); let mut sc = IO::new(r.lock(), w.lock());

let n: usize = sc.read();
let map: Vec<Vec<char>> = (0..n).map(|_| sc.chars()).collect();

let mut dp = vec![vec![vec![vec![INF; n + 1]; n]; n + 1]; n];

let ans = calc(&map, 0, n, 0, n, &mut dp);
println!("{}", ans);

}

fn calc( map: &Vec<Vec>, r_from: usize, r_to: usize, c_from: usize, c_to: usize, memo: &mut Vec<Vec<Vec<Vec>>>, ) -> i64 { let dr = r_to - r_from; let dc = c_to - c_from; if dr.min(dc) == 0 { return 0; } if memo[r_from][r_to][c_from][c_to] < INF { return memo[r_from][r_to][c_from][c_to]; }

let mut min_cost = dr.max(dc) as i64;
for i in r_from..r_to {
    if (c_from..c_to).all(|j| map[i][j] == '.') {
        let head = calc(map, r_from, i, c_from, c_to, memo);
        let tail = calc(map, i + 1, r_to, c_from, c_to, memo);
        min_cost = min_cost.min(head + tail);
    }
}

for j in c_from..c_to {
    if (r_from..r_to).all(|i| map[i][j] == '.') {
        let left = calc(map, r_from, r_to, c_from, j, memo);
        let right = calc(map, r_from, r_to, j + 1, c_to, memo);
        min_cost = min_cost.min(left + right);
    }
}

memo[r_from][r_to][c_from][c_to] = min_cost;
min_cost

}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> { pub fn new(r: R, w: W) -> IO<R, W> { IO(r, std::io::BufWriter::new(w)) } pub fn write<S: ToString>(&mut self, s: S) { use std::io::Write; self.1.write_all(s.to_string().as_bytes()).unwrap(); } pub fn read<T: std::str::FromStr>(&mut self) -> T { use std::io::Read; let buf = self .0 .by_ref() .bytes() .map(|b| b.unwrap()) .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t') .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t') .collect::<Vec<>>(); unsafe { std::str::from_utf8_unchecked(&buf) } .parse() .ok() .expect("Parse error.") } pub fn usize0(&mut self) -> usize { self.read::() - 1 } pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec { (0..n).map(|| self.read()).collect() } pub fn chars(&mut self) -> Vec { self.read::().chars().collect() } }

||<

Put "open" to your class and its method when you get a NullPointerException by mocking your class by Mockito.

Problem

When you have MyClass and try to write a test by mocking MyClass as the following, you will get an NPE:

MyClass:

open class MyClass {
    fun createList(string: String): List<String> {
        return listOf("A", "B", "C", string)
    }
}

Mocking MyClass by Mockito:

import org.junit.jupiter.api.Test
import org.mockito.kotlin.any
import org.mockito.kotlin.mock
import org.mockito.kotlin.whenever

class TestMyClass {
    @Test
    fun testMyClass() {
        val mock = mock<MyClass>()
        whenever(mock.createList(any())).thenReturn(emptyList())
    }
}

Exception you will get:

java.lang.NullPointerException: Parameter specified as non-null is null: method MyClass.createList, parameter string

Solution: Put "open" not only to your class but also to the method

open class MyClass {
+   open fun createList(string: String): List<String> {
-   fun createList(string: String): List<String> {
        return listOf("A", "B", "C", string)
    }
}

2021/11/21

ARC129A - Smaller XOR

atcoder.jp

頑張って桁DPをやっていて、解説を読んで崩れ落ちた…

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: i64 = sc.read();
    let l: i64 = sc.read();
    let r: i64 = sc.read();
    let ans = solve(n, r) - solve(n, l - 1);
    println!("{}", ans);
}

fn solve(n: i64, max: i64) -> i64 {
    let mut dp = vec![vec![vec![0; 2]; 2]; 2];
    dp[0][0][0] = 1;
    for pos in (0..63).rev() {
        let max_d = (max >> pos) & 1;
        let n_d = (n >> pos) & 1;

        let mut next = vec![vec![vec![0; 2]; 2]; 2];
        for started in 0..2 {
            let is_started = started == 1;
            for lower in 0..2 {
                let is_lower = lower == 1;

                for xor_lower in 0..2 {
                    for next_digit in 0..2 {
                        let next_started = if is_started || next_digit == 1 { 1 } else { 0 };
                        let next_lower = if is_lower || max_d > next_digit { 1 } else { 0 };
                        let next_n_lower = if xor_lower == 1 || (next_digit == 1 && n_d == 1) {
                            1
                        } else {
                            0
                        };

                        if next_lower != 1 && max_d < next_digit {
                            continue;
                        }
                        if next_n_lower != 1 && next_digit == 1 {
                            continue;
                        }

                        next[next_started][next_lower][next_n_lower] +=
                            dp[started][lower][xor_lower];
                    }
                }
            }
        }

        dp = next;
        // eprintln!("{:?}", dp);
    }

    let ans = dp[1][0][1] + dp[1][1][1];
    ans
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC129D - -1+2-1

atcoder.jp

面白かった。数列に対する操作を行う時、数列そのものの変化よりも、その数列の階差数列の変化を観察した方が分かりやすくなることがある。この問題はその逆バージョンで、与えられた数列が階差数列だとして、元の数列に対する変化がどのようなものか考えることで解ける。

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let a: Vec<i64> = sc.vec(n);

    if a.iter().sum::<i64>() != 0 {
        println!("-1");
        return;
    }

    let mut b = vec![0; n];
    for i in 1..n {
        b[i] = b[i - 1] + a[i - 1];
    }
    assert_eq!(b[0], 0);
    assert_eq!(b[n - 1] + a[n - 1], 0);

    let b_sum = b.iter().sum::<i64>();
    if b_sum % (n as i64) != 0 {
        println!("-1");
        return;
    }

    let one = b_sum / (n as i64);
    for b in b.iter_mut() {
        *b -= one;
    }

    let mut ans = 0;
    let mut carry = 0;
    for i in 0..(3 * n) {
        if b[i % n] > 0 {
            carry += b[i % n];
            b[i % n] = 0;
        } else {
            let t = carry.min(-b[i % n]);
            carry -= t;
            b[i % n] += t;
        }
        ans += carry;
    }
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC129C - Multiple of 7

atcoder.jp

「文字列の[l..r]を切り出して数としてみた時、これがxの倍数となっている」というのは [0..l]00000... と [0..r]000... を割ったあまりが等しいことを意味する。例えば1234567789の77の部分が7の倍数であるのは、1234560000と1234567700のあまりが等しいことと同値。これを見つけられずに謎の解法で殴り倒してしまった。

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: i64 = sc.read();
    let ans = solve(n);
    for ans in ans {
        sc.write(ans);
    }
    sc.write('\n');
}

fn solve(n: i64) -> Vec<i64> {
    let mut c = vec![];
    let mut z = n;
    while z > 0 {
        let x = (z as f64 + 100.0).sqrt() as i64 * 2;
        for k in (1..=x).rev() {
            if k * (k - 1) / 2 <= z {
                c.push(k);
                z -= k * (k - 1) / 2;
                break;
            }
        }
    }
    assert!(c.len() <= 7, "n={} c={:?}", n, c);

    let mut b = vec![];
    for (target, count) in c.into_iter().enumerate() {
        let target = target as i64;
        let count = if target == 0 { count - 1 } else { count };
        for _ in 0..count {
            b.push(target);
        }
    }
    b.push(0);
    b.reverse();

    let n = b.len();
    let mut ans = vec![];
    let mut pow10 = 1;
    for i in (1..n).rev() {
        let prev = b[i - 1];
        let next = b[i];

        for x in 1.. {
            assert!(x < 10);
            if (prev + x * pow10) % 7 == next {
                ans.push(x);
                break;
            }
        }

        pow10 = (pow10 * 10) % 7;
    }

    ans.reverse();
    ans
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021/11/17

Codeforces Round #751 (Div. 1) C. Optimal Insertion

codeforces.com

とりあえずbはソートしても良いことが分かって、aに挿入された後のb全体で見てもソートされていることが分かる。すると、bを小さい順にaに挿入していくと、既に挿入されたbの値と後から挿入されるbの値はお互いに影響しないことが分かる。よって、各biの挿入は独立に考えてよく、biは挿入した際に増える反点数が最小であるような位置に挿入すれば良い。複数ある場合は一番前にすると無難。

use crate::fenwick_tree::FenwickTree;
use crate::lazy_segment_tree::LazySegmentTree;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let t: usize = sc.read();
    for _ in 0..t {
        let n: usize = sc.read();
        let m: usize = sc.read();

        let mut a = Vec::with_capacity(n);
        for i in 0..n {
            let x: i64 = sc.read();
            a.push((x, i));
        }

        let mut b: Vec<i64> = sc.vec(m);
        a.sort();
        b.sort();
        let ans = solve(a, b);
        sc.write(ans);
        sc.write('\n');
    }
}
const INF: i64 = 1 << 60;

fn solve(a: Vec<(i64, usize)>, b: Vec<i64>) -> i64 {
    let n = a.len() + 1;
    let mut min_seg = LazySegmentTree::new(
        n,
        || (INF, n),
        |&s: &(i64, usize), &t: &(i64, usize)| s.min(t),
        |&f, &(x, i)| (f + x, i),
        |&f, &g| f + g,
        || 0,
    );

    for i in 0..n {
        min_seg.set(i, (0, i));
    }

    for i in 0..(n - 1) {
        min_seg.apply_range((i + 1)..n, 1);
    }

    let mut cost = 0;
    let mut a_cur = 0;
    let mut b_cur = 0;
    while a_cur < a.len() {
        let mut tt = 0;
        while b_cur < b.len() && b[b_cur] < a[a_cur].0 {
            b_cur += 1;
            tt += 1;
        }
        if tt > 0 {
            let (x, _) = min_seg.prod(0..n);
            cost += tt * x;
        }

        let mut next = a_cur;
        while next < a.len() && a[a_cur].0 == a[next].0 {
            next += 1;
        }

        for i in a_cur..next {
            let (_, i) = a[i];
            min_seg.apply_range((i + 1)..n, -1);
        }

        if b_cur < b.len() && b[b_cur] == a[a_cur].0 {
            let mut b_next = b_cur;
            while b_next < b.len() && b[b_cur] == b[b_next] {
                b_next += 1;
            }

            let count = b_next - b_cur;
            let (x, _) = min_seg.prod(0..n);
            cost += x * count as i64;
            b_cur = b_next;
        }

        for i in a_cur..next {
            let (_, i) = a[i];
            min_seg.apply_range(0..i, 1);
        }

        a_cur = next;
    }

    let mut tt = b.len() - b_cur;
    if tt > 0 {
        let (x, _) = min_seg.prod(0..n);
        cost += tt as i64 * x;
    }

    let mut bit = FenwickTree::new(n, || 0);
    let mut s = 0;

    for (_, i) in a {
        s += bit.sum(i, n);
        bit.add(i, 1);
    }
    cost + s
}
pub mod fenwick_tree {
    /// `FenwickTree` is a data structure that can efficiently update elements
    /// and calculate prefix sums in a table of numbers.
    /// [https://en.wikipedia.org/wiki/Fenwick_tree](https://en.wikipedia.org/wiki/Fenwick_tree)
    pub struct FenwickTree<T, F> {
        n: usize,
        data: Vec<T>,
        initialize: F,
    }

    impl<T, F> FenwickTree<T, F>
    where
        T: Copy + std::ops::AddAssign + std::ops::Sub<Output = T>,
        F: Fn() -> T,
    {
        /// Constructs a new `FenwickTree`. The size of `FenwickTree` should be specified by `size`.
        pub fn new(size: usize, initialize: F) -> FenwickTree<T, F> {
            FenwickTree {
                n: size + 1,
                data: vec![initialize(); size + 1],
                initialize,
            }
        }

        pub fn add(&mut self, k: usize, value: T) {
            let mut x = k;
            while x < self.n {
                self.data[x] += value;
                x |= x + 1;
            }
        }

        /// Returns a sum of range `[l, r)`
        pub fn sum(&self, l: usize, r: usize) -> T {
            self.sum_one(r) - self.sum_one(l)
        }

        /// Returns a sum of range `[0, k)`
        pub fn sum_one(&self, k: usize) -> T {
            assert!(k < self.n, "Cannot calculate for range [{}, {})", k, self.n);
            let mut result = (self.initialize)();
            let mut x = k as i32 - 1;
            while x >= 0 {
                result += self.data[x as usize];
                x = (x & (x + 1)) - 1;
            }

            result
        }
    }
}

pub mod lazy_segment_tree {
    type Range = std::ops::Range<usize>;

    pub struct LazySegmentTree<S, Op, E, F, Mapping, Composition, Id> {
        n: usize,
        size: usize,
        log: usize,
        data: Vec<S>,
        lazy: Vec<F>,
        op: Op,
        e: E,
        mapping: Mapping,
        composition: Composition,
        id: Id,
    }

    impl<S, Op, E, F, Mapping, Composition, Id> LazySegmentTree<S, Op, E, F, Mapping, Composition, Id>
    where
        S: Clone,
        E: Fn() -> S,
        F: Clone,
        Op: Fn(&S, &S) -> S,
        Mapping: Fn(&F, &S) -> S,
        Composition: Fn(&F, &F) -> F,
        Id: Fn() -> F,
    {
        pub fn new(
            n: usize,
            e: E,
            op: Op,
            mapping: Mapping,
            composition: Composition,
            id: Id,
        ) -> Self {
            let size = n.next_power_of_two() as usize;
            LazySegmentTree {
                n,
                size,
                log: size.trailing_zeros() as usize,
                data: vec![e(); 2 * size],
                lazy: vec![id(); size],
                e,
                op,
                mapping,
                composition,
                id,
            }
        }
        pub fn set(&mut self, mut index: usize, value: S) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = value;
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }

        pub fn get(&mut self, mut index: usize) -> S {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index].clone()
        }

        pub fn prod(&mut self, range: Range) -> S {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l < r && r <= self.n);

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push(r >> i);
                }
            }

            let mut sum_l = (self.e)();
            let mut sum_r = (self.e)();
            while l < r {
                if l & 1 != 0 {
                    sum_l = (self.op)(&sum_l, &self.data[l]);
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    sum_r = (self.op)(&self.data[r], &sum_r);
                }
                l >>= 1;
                r >>= 1;
            }

            (self.op)(&sum_l, &sum_r)
        }

        pub fn all_prod(&self) -> S {
            self.data[1].clone()
        }

        pub fn apply(&mut self, mut index: usize, f: F) {
            assert!(index < self.n);
            index += self.size;
            for i in (1..=self.log).rev() {
                self.push(index >> i);
            }
            self.data[index] = (self.mapping)(&f, &self.data[index]);
            for i in 1..=self.log {
                self.update(index >> i);
            }
        }
        pub fn apply_range(&mut self, range: Range, f: F) {
            let mut l = range.start;
            let mut r = range.end;
            assert!(l <= r && r <= self.n);
            if l == r {
                return;
            }

            l += self.size;
            r += self.size;

            for i in (1..=self.log).rev() {
                if ((l >> i) << i) != l {
                    self.push(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.push((r - 1) >> i);
                }
            }

            {
                let mut l = l;
                let mut r = r;
                while l < r {
                    if l & 1 != 0 {
                        self.all_apply(l, f.clone());
                        l += 1;
                    }
                    if r & 1 != 0 {
                        r -= 1;
                        self.all_apply(r, f.clone());
                    }
                    l >>= 1;
                    r >>= 1;
                }
            }

            for i in 1..=self.log {
                if ((l >> i) << i) != l {
                    self.update(l >> i);
                }
                if ((r >> i) << i) != r {
                    self.update((r - 1) >> i);
                }
            }
        }

        fn update(&mut self, k: usize) {
            self.data[k] = (self.op)(&self.data[2 * k], &self.data[2 * k + 1]);
        }
        fn all_apply(&mut self, k: usize, f: F) {
            self.data[k] = (self.mapping)(&f, &self.data[k]);
            if k < self.size {
                self.lazy[k] = (self.composition)(&f, &self.lazy[k]);
            }
        }
        fn push(&mut self, k: usize) {
            self.all_apply(2 * k, self.lazy[k].clone());
            self.all_apply(2 * k + 1, self.lazy[k].clone());
            self.lazy[k] = (self.id)();
        }
    }
}
pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021/11/16

ABC155E - Payment

atcoder.jp

桁DPは前の桁から、という思い込みがあって全然見えなかった…頭が固い……

const INF: usize = 1 << 60;
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: Vec<usize> = sc
        .read::<String>()
        .bytes()
        .map(|b| b as usize - b'0' as usize)
        .collect();

    let mut dp = vec![0, INF];
    for d in n.into_iter().rev() {
        let mut next = vec![INF; 2];
        for carry in 0..2 {
            let pay = carry + d;
            if pay < 10 {
                next[0] = next[0].min(dp[carry] + pay);
            }
            next[1] = next[1].min(dp[carry] + 10 - pay);
        }
        dp = next;
    }

    let ans = dp[0].min(dp[1] + 1);
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

AGC037D - Sorting a Grid

atcoder.jp

各列ごとに順番にマッチングをしていくと終盤で詰んでしまわないか?というところから先に進まなかった。具体的に詰むような終盤の状態を構築しようとするとできないことはすぐに分かるので、具体例を考えてみるべきだった。

use crate::dinitz::Dinitz;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let m: usize = sc.read();
    let mut a: Vec<Vec<usize>> = vec![vec![0; m]; n];
    for i in 0..n {
        for j in 0..m {
            a[i][j] = sc.usize0();
        }
    }

    let mut used = vec![vec![false; m]; n];
    let mut edge_id = vec![vec![0; m]; n];
    let mut columns = vec![];
    for _ in 0..m {
        let mut graph = Dinitz::new(2 * n + 2);
        let source = 2 * n;
        let sink = 2 * n + 1;
        for i in 0..n {
            graph.add_edge(source, i, 1);
            graph.add_edge(i + n, sink, 1);
        }

        for i in 0..n {
            for j in 0..m {
                if used[i][j] {
                    continue;
                }

                let target_row = a[i][j] / m;
                edge_id[i][j] = graph.g[i].len();
                graph.add_edge(i, target_row + n, 1);
            }
        }

        let flow = graph.max_flow(source, sink);
        assert_eq!(flow as usize, n);

        let mut column = vec![];
        for i in 0..n {
            for j in 0..m {
                if used[i][j] {
                    continue;
                }

                let ej = edge_id[i][j];
                if graph.g[i][ej].cap == 0 {
                    used[i][j] = true;
                    column.push(a[i][j]);
                }
            }
        }

        assert_eq!(column.len(), n);
        columns.push(column);
    }

    for i in 0..n {
        for j in 0..m {
            if j > 0 {
                sc.write(' ');
            }
            sc.write(columns[j][i] + 1);
        }
        sc.write('\n');
    }

    for column in columns.iter_mut() {
        column.sort();
    }
    for i in 0..n {
        for j in 0..m {
            if j > 0 {
                sc.write(' ');
            }
            sc.write(columns[j][i] + 1);
        }
        sc.write('\n');
    }
}
pub mod dinitz {
    const INF: i64 = 1 << 60;
    pub struct Edge {
        pub to: usize,
        pub rev: usize,
        pub is_reversed: bool,
        pub cap: i64,
    }

    pub struct Dinitz {
        pub g: Vec<Vec<Edge>>,
    }

    impl Dinitz {
        pub fn new(v: usize) -> Dinitz {
            let mut g: Vec<Vec<Edge>> = Vec::new();
            for _ in 0..v {
                g.push(Vec::new());
            }
            Dinitz { g }
        }

        pub fn add_edge(&mut self, from: usize, to: usize, cap: i64) {
            let to_len = self.g[to].len();
            let from_len = self.g[from].len();
            self.g[from].push(Edge {
                to,
                rev: to_len,
                is_reversed: false,
                cap,
            });
            self.g[to].push(Edge {
                to: from,
                rev: from_len,
                is_reversed: true,
                cap: 0,
            });
        }

        fn dfs(
            &mut self,
            v: usize,
            sink: usize,
            flow: i64,
            level: &[i32],
            iter: &mut [usize],
        ) -> i64 {
            if v == sink {
                return flow;
            }
            while iter[v] < self.g[v].len() {
                let flow = std::cmp::min(flow, self.g[v][iter[v]].cap);
                let to = self.g[v][iter[v]].to;
                if flow > 0 && level[v] < level[to] {
                    let flowed = self.dfs(to, sink, flow, level, iter);
                    if flowed > 0 {
                        let rev = self.g[v][iter[v]].rev;
                        self.g[v][iter[v]].cap -= flowed;
                        self.g[to][rev].cap += flowed;
                        return flowed;
                    }
                }
                iter[v] += 1;
            }
            0
        }

        fn bfs(&self, s: usize) -> Vec<i32> {
            let v = self.g.len();
            let mut level = vec![-1; v];
            level[s] = 0;
            let mut deque = std::collections::VecDeque::new();
            deque.push_back(s);
            while let Some(v) = deque.pop_front() {
                for e in self.g[v].iter() {
                    if e.cap > 0 && level[e.to] < 0 {
                        level[e.to] = level[v] + 1;
                        deque.push_back(e.to);
                    }
                }
            }
            level
        }

        pub fn max_flow(&mut self, s: usize, t: usize) -> i64 {
            let v = self.g.len();
            let mut flow: i64 = 0;
            loop {
                let level = self.bfs(s);
                if level[t] < 0 {
                    return flow;
                }
                let mut iter = vec![0; v];
                loop {
                    let f = self.dfs(s, t, INF, &level, &mut iter);
                    if f == 0 {
                        break;
                    }
                    flow += f;
                }
            }
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

2021/11/14

ABC227G - Divisors of Binomial Coefficient

atcoder.jp

ついに区間篩を知らなかったことが仇に…

 [2, X] の素数を求めながら  [Y, X^{2}] の素因数分解もできるの、言われてみればそうなんだけど、すごい。

use crate::mod_int::ModInt;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let k: usize = sc.read();

    let from = n - k + 1;
    let to = n;

    let sq_n = (n as f64).sqrt() as usize + 1;
    let l = k.max(sq_n);
    let mut divisors = vec![vec![]; l + 1];
    let mut divisors_big = vec![vec![]; k];
    for p in 2..=l {
        if divisors[p].is_empty() {
            let mut cur = p;
            while cur <= l {
                divisors[cur].push(p);
                cur += p;
            }

            let mut cur = (from + p - 1) / p * p;
            while cur <= to {
                divisors_big[cur - from].push(p);
                cur += p;
            }
        }
    }

    let mut big_primes = 0;
    let mut count = vec![0; l + 1];
    for i in 1..=k {
        let mut lower = i;
        for &prime in divisors[i].iter() {
            while lower % prime == 0 {
                lower /= prime;
                count[prime] -= 1;
            }
        }

        let mut upper = n - i + 1;
        for &prime in divisors_big[n - i + 1 - from].iter() {
            while upper % prime == 0 {
                upper /= prime;
                count[prime] += 1;
            }
        }

        if upper > 1 {
            big_primes += 1;
        }
    }

    let mut ans = ModInt::from(1);
    for c in count {
        assert!(c >= 0, "{}", c);
        ans *= c + 1;
    }
    ans *= ModInt::from(2).pow(big_primes);
    println!("{}", ans.value());
}

pub mod mod_int {
    type ModInternalNum = i64;
    thread_local!(
        static MOD: std::cell::RefCell<ModInternalNum> = std::cell::RefCell::new(0);
    );

    pub fn set_mod_int<T: ToInternalNum>(v: T) {
        MOD.with(|x| x.replace(v.to_internal_num()));
    }
    fn modulo() -> ModInternalNum {
        998244353
    }

    pub struct ModInt(ModInternalNum);
    impl Clone for ModInt {
        fn clone(&self) -> Self {
            Self(self.0)
        }
    }
    impl Copy for ModInt {}

    impl ModInt {
        fn internal_new(mut v: ModInternalNum) -> Self {
            let m = modulo();
            if v >= m {
                v %= m;
            }
            Self(v)
        }

        pub fn internal_pow(&self, mut e: ModInternalNum) -> Self {
            let mut result = 1;
            let mut cur = self.0;
            let modulo = modulo();
            while e > 0 {
                if e & 1 == 1 {
                    result *= cur;
                    result %= modulo;
                }
                e >>= 1;
                cur = (cur * cur) % modulo;
            }
            Self(result)
        }

        pub fn pow<T>(&self, e: T) -> Self
        where
            T: ToInternalNum,
        {
            self.internal_pow(e.to_internal_num())
        }

        pub fn value(&self) -> ModInternalNum {
            self.0
        }
    }

    pub trait ToInternalNum {
        fn to_internal_num(&self) -> ModInternalNum;
    }
    impl ToInternalNum for ModInt {
        fn to_internal_num(&self) -> ModInternalNum {
            self.0
        }
    }
    macro_rules! impl_primitive {
        ($primitive:ident) => {
            impl From<$primitive> for ModInt {
                fn from(v: $primitive) -> Self {
                    let v = v as ModInternalNum;
                    Self::internal_new(v)
                }
            }
            impl ToInternalNum for $primitive {
                fn to_internal_num(&self) -> ModInternalNum {
                    *self as ModInternalNum
                }
            }
        };
    }
    impl_primitive!(u8);
    impl_primitive!(u16);
    impl_primitive!(u32);
    impl_primitive!(u64);
    impl_primitive!(usize);
    impl_primitive!(i8);
    impl_primitive!(i16);
    impl_primitive!(i32);
    impl_primitive!(i64);
    impl_primitive!(isize);

    impl<T: ToInternalNum> std::ops::AddAssign<T> for ModInt {
        fn add_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }

            self.0 += rhs;
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }

    impl<T: ToInternalNum> std::ops::Add<T> for ModInt {
        type Output = ModInt;
        fn add(self, rhs: T) -> Self::Output {
            let mut res = self;
            res += rhs;
            res
        }
    }
    impl<T: ToInternalNum> std::ops::SubAssign<T> for ModInt {
        fn sub_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            if rhs > 0 {
                self.0 += m - rhs;
            }
            if self.0 >= m {
                self.0 -= m;
            }
        }
    }
    impl<T: ToInternalNum> std::ops::Sub<T> for ModInt {
        type Output = Self;
        fn sub(self, rhs: T) -> Self::Output {
            let mut res = self;
            res -= rhs;
            res
        }
    }
    impl<T: ToInternalNum> std::ops::MulAssign<T> for ModInt {
        fn mul_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            self.0 *= rhs;
            self.0 %= m;
        }
    }
    impl<T: ToInternalNum> std::ops::Mul<T> for ModInt {
        type Output = Self;
        fn mul(self, rhs: T) -> Self::Output {
            let mut res = self;
            res *= rhs;
            res
        }
    }

    impl<T: ToInternalNum> std::ops::DivAssign<T> for ModInt {
        fn div_assign(&mut self, rhs: T) {
            let mut rhs = rhs.to_internal_num();
            let m = modulo();
            if rhs >= m {
                rhs %= m;
            }
            let inv = Self(rhs).internal_pow(m - 2);
            self.0 *= inv.value();
            self.0 %= m;
        }
    }

    impl<T: ToInternalNum> std::ops::Div<T> for ModInt {
        type Output = Self;
        fn div(self, rhs: T) -> Self::Output {
            let mut res = self;
            res /= rhs;
            res
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}

ARC067F - Yakiniku Restaurants

atcoder.jp

[from, to) で利用できるものについて、N x N の2次元平面上にプロットしてみると、長方形領域の集合になっているという問題。直線上を移動する問題を2次元にプロットするところに発想の飛躍があるように感じたが、典型的な考え方かもしれない。ものにしたい。

use crate::sparse_table::SparseTable;
use std::collections::VecDeque;

fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());

    let n: usize = sc.read();
    let m: usize = sc.read();
    let a: Vec<i64> = sc.vec(n - 1);
    let mut pos = vec![0; n];
    for i in 1..n {
        pos[i] = pos[i - 1] + a[i - 1];
    }

    let b: Vec<Vec<i64>> = (0..n).map(|_| sc.vec(m)).collect();

    let mut available = vec![vec![]; n];

    for ticket_id in 0..m {
        let b = (0..n).map(|j| (b[j][ticket_id], j)).collect::<Vec<_>>();
        let st = SparseTable::from(&b, (0, n), |a, b| a.max(b));

        let mut segments = VecDeque::new();
        segments.push_back((0, n));
        while let Some((from, to)) = segments.pop_front() {
            let (x, i) = st.get(from, to);
            available[from].push((i, ticket_id, x));
            if from < i {
                segments.push_back((from, i));
            }
            if i + 1 < to {
                segments.push_back((i + 1, to));
            }
        }
    }

    let mut ans = 0;
    let mut events = vec![vec![]; n];
    for from in 0..n {
        for &(i, ticket_id, x) in available[from].iter() {
            events[i].push((ticket_id, x));
        }

        let mut tickets = vec![0; m];
        let mut sum = 0;
        for i in 0..m {
            tickets[i] = b[from][i];
            sum += tickets[i];
        }
        for to in from..n {
            for &(i, x) in events[to].iter() {
                sum -= tickets[i];
                tickets[i] = x;
                sum += tickets[i];
            }

            let d = pos[to] - pos[from];
            ans = ans.max(sum - d);
        }
    }

    println!("{}", ans);
}
pub mod sparse_table {
    pub struct SparseTable<T, F> {
        data: Vec<Vec<T>>,
        op: F,
    }

    impl<T, F> SparseTable<T, F>
    where
        T: Copy,
        F: Fn(T, T) -> T,
    {
        pub fn from(v: &[T], init: T, op: F) -> Self {
            let size = v.len().next_power_of_two();
            let count = size.trailing_zeros() as usize + 1;
            let mut data = vec![vec![init; size]; count];
            for (i, v) in v.iter().cloned().enumerate() {
                data[0][i] = v;
            }
            for c in 1..count {
                for i in 0..size {
                    let next = std::cmp::min(size - 1, i + (1 << (c - 1)));
                    data[c][i] = op(data[c - 1][i], data[c - 1][next]);
                }
            }

            Self { data, op }
        }

        /// get the result for [l, r)
        pub fn get(&self, l: usize, r: usize) -> T {
            assert!(l < r);
            let length = r - l;
            if length == 1 {
                return self.data[0][l];
            }
            let block_size = length.next_power_of_two() >> 1;
            let c = block_size.trailing_zeros() as usize;
            let left = self.data[c][l];
            let right = self.data[c][r - block_size];
            (self.op)(left, right)
        }
    }
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: ToString>(&mut self, s: S) {
        use std::io::Write;
        self.1.write_all(s.to_string().as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn usize0(&mut self) -> usize {
        self.read::<usize>() - 1
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}