Submission #68216359

---

Source Code Expand

// Takahashi's Expectation
#![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 Present = (i64, i64, i64);

fn read_present() -> Present {
	let v: Vec<i64> = read_vec();
	let (P, A, B) = (v[0], v[1], v[2]);
	(P, A, B)
}

fn read_input() -> (Vec<Present>, usize) {
	let N: usize = read();
	let presents: Vec<Present> = (0..N).map(|_| read_present()).collect();
	let Q: usize = read();
	(presents, Q)
}

fn make_DP(presents: &Vec<Present>) -> Vec<Vec<i64>> {
	let N = presents.len();
	let M = presents.iter().map(|&(P, A, _)| P+A).max().unwrap();
	let mut dp: Vec<Vec<i64>> = vec![vec![0; M as usize + 1]; N+1];
	dp[N] = (0..M+1).collect();
	for n in (0..N).rev() {
		let (P, A, B) = presents[n];
		for x in 0..M+1 {
			if x <= P {
				dp[n][x as usize] = dp[n+1][(x+A) as usize];
			}
			else {
				dp[n][x as usize] = dp[n+1][max(0, x-B) as usize]
			}
		}
	}
	dp
}

fn accumulate(v: &Vec<i64>) -> Vec<i64> {
	let N = v.len();
	let mut a: Vec<i64> = vec![0; N+1];
	for n in 0..N {
		a[n+1] = a[n] + v[n]
	}
	a
}

fn bin_search(x: i64, first: usize, last: usize, acc: &Vec<i64>) -> usize {
	let mid = (first + last) / 2;
	if last - first == 1 {
		first
	}
	else if last - first == 2 {
		if acc[first] >= x {
			first
		}
		else {
			first + 1
		}
	}
	else if acc[mid] >= x {
		bin_search(x, first, mid + 1, acc)
	}
	else {
		bin_search(x, mid + 1, last, acc)
	}
}

fn F_each(X: i64, dp: &Vec<Vec<i64>>, acc_B: &Vec<i64>) -> i64 {
	let N = dp.len() - 1;
	let M = dp[0].len() as i64;
	if X < M {
		dp[0][X as usize]
	}
	else if X > acc_B[N-1] + M - 1 {
		X - acc_B[N]
	}
	else {
		let n = bin_search(X - M + 1, 0, N + 1, acc_B);
		if n == 0 {
//			X - acc_B[n]
			X
		}
		else {
			let x = X - acc_B[n];
			dp[n][x as usize]
		}
	}
}

fn F(presents: Vec<Present>, Q: usize) {
	let dp = make_DP(&presents);
	let v: Vec<i64> = presents.iter().map(|&(_, _, B)| B).collect::<Vec<_>>();
	let acc_B = accumulate(&v);
	for _ in 0..Q {
		let X: i64 = read();
		println!("{}", F_each(X, &dp, &acc_B))
	}
}

fn main() {
	let (presents, Q) = read_input();
	F(presents, Q)
}

Submission Info

Judge Result