AtCoder Beginner Contest 364 E

https://atcoder.jp/contests/abc364/tasks/abc364_e

計算量が多そうですが、xが小さいほうから見ていって、yが小さくならないものは捨てられるので、意外とたくさん捨てられるようです。

// Maximum Glutton
#![allow(non_snake_case)]


//////////////////// 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()
}


//////////////////// Point ////////////////////

#[derive(Clone, Copy, Ord, PartialOrd, Eq, PartialEq)]
struct Point {
    x: i32,
    y: i32
}

use std::ops::{Add, AddAssign};

impl Add for Point {
    type Output = Self;
    
    fn add(self, other: Self) -> Self {
        let x = self.x + other.x;
        let y = self.y + other.y;
        Point { x, y }
    }
}

impl AddAssign for Point {
    fn add_assign(&mut self, other: Self) {
        self.x += other.x;
        self.y += other.y
    }
}

impl Point {
    fn new(x: i32, y: i32) -> Point {
        Point { x, y }
    }
    
    fn read() -> Point {
        let v = read_vec();
        Point::new(v[0], v[1])
    }
}


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

fn read_input() -> (i32, i32, Vec<Point>) {
    let v: Vec<usize> = read_vec();
    let N = v[0];
    let (X, Y) = (v[1] as i32, v[2] as i32);
    let points: Vec<Point> = (0..N).map(|_| Point::read()).collect();
    (X, Y, points)
}

fn max_num_within(points: &Vec<Point>, X: i32, Y: i32) -> Vec<Vec<Point>> {
    if points.len() == 1 {
        let mut v: Vec<Vec<Point>> = vec![vec![Point::new(0, 0)]];
        if points[0].x <= X && points[0].y <= Y {
            v.push(vec![points[0]])
        }
        v
    }
    else {
        let mid = points.len() / 2;
        let v1 = max_num_within(&points[..mid].to_vec(), X, Y);
        let v2 = max_num_within(&points[mid..].to_vec(), X, Y);
        let mut v: Vec<Vec<Point>> = vec![];
        for (n1, pts1) in v1.iter().enumerate() {
            for (n2, pts2) in v2.iter().enumerate() {
                let n = n1 + n2;
                while n >= v.len() {
                    v.push(vec![])
                }
                for pt1 in pts1.iter() {
                    for pt2 in pts2.iter() {
                        let pt = *pt1 + *pt2;
                        if pt.x <= X && pt.y <= Y {
                            v[n].push(*pt1 + *pt2)
                        }
                    }
                }
            }
        }
        
        for i in 0..v.len() {
            if v[i].is_empty() {
                continue
            }
            v[i].sort();
            let mut w = vec![];
            let mut max_y = v[i][0].y + 1;
            for pt in v[i].iter() {
                if pt.y < max_y {
                    w.push(*pt);
                    max_y = pt.y
                }
            }
            v[i] = w
        }
        
        for j in (0..v.len()).rev() {
            if !v[j].is_empty() {
                break
            }
            let _ = v.pop();
        }
        
        v
    }
}

fn F(X: i32, Y: i32, points: Vec<Point>) -> usize {
    let N = points.len();
    let mut sum_pt = Point::new(0, 0);
    for point in points.iter() {
        sum_pt += *point
    }
    if sum_pt.x <= X && sum_pt.y <= Y {
        N
    }
    else {
        let v = max_num_within(&points, X, Y);
        v.len()
    }
}

fn main() {
    let (X, Y, points) = read_input();
    println!("{}", F(X, Y, points))
}