AtCoder Beginner Contest 333 E

https://atcoder.jp/contests/abc333/tasks/abc333_e

タイプが違うと独立に考えられます。タイプトごとに、逆向きに、符号も逆にして考えます。トータルで負になるときだけ、パスします。

// Takahashi Quest
#![allow(non_snake_case)]

use std::cmp::max;


//////////////////// library ////////////////////

fn read<T: std::str::FromStr>() -> T {
    let mut line = String::new();
    std::io::stdin().read_line(&mut line).ok();
    line.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>().split_whitespace()
            .map(|e| e.parse().ok().unwrap()).collect()
}


//////////////////// process ////////////////////

type Query = (usize, i64);  // (x, inc)

fn read_query() -> Query {
    let v = read_vec::<i64>();
    let (t, x) = (v[0], v[1] as usize);
    (x-1, if t == 1 { 1 } else { -1 })
}

fn read_input() -> Vec<Query> {
    let N: usize = read();
    let queries: Vec<Query> = (0..N).map(|_| read_query()).collect();
    queries
}

fn F(queries: Vec<Query>) {
    let N = queries.len();
    let mut s = vec![0; N];
    let mut max_sum = 0;
    let mut cur_sum = 0;
    let mut v: Vec<i64> = vec![];
    for (x, inc) in queries.into_iter().rev() {
        if s[x] - inc < 0 {
            v.push(0);
        }
        else {
            s[x] -= inc;
            cur_sum -= inc;
            if inc < 0 {
                max_sum = max(max_sum, cur_sum);
            }
            else {
                v.push(1)
            }
        }
    }
    
    if cur_sum > 0 { 
        println!("-1")
    }
    else {
        println!("{}", max_sum);
        println!("{}", v.iter().rev().map(|&i| i.to_string()).
                                collect::<Vec<_>>().join(" "))
    }
}

fn main() {
    let queries = read_input();
    F(queries)
}