#P17500. [ICPC 2026 Wuhan I] Rectangle Cutting
[ICPC 2026 Wuhan I] Rectangle Cutting
题目描述
八千代在平面直角坐标系的第一象限内有一个矩形。该矩形的左下角位于坐标原点 ,右上角位于 。换言之,矩形的两边分别与 轴、 轴重合,其在 轴方向的长度为 ,在 轴方向的长度为 。
八千代决定把这个矩形切 刀。具体地,她有以下两种切割方式:
- 横向切割:给定一个正整数 ,沿着直线 进行切割。
- 纵向切割:给定一个正整数 ,沿着直线 进行切割。
每次切割都会贯穿整个区域,将现有的矩形进一步切割成更多的小矩形。
八千代想要知道,在每一次切割完成之后,当前所有被切分出来的小矩形中,面积的最大值是多少?
输入格式
第一行包含三个整数 (,),分别表示初始矩形的水平长度、垂直长度以及切割的次数。
接下来 行,每行包含两个整数 ,描述一次切割操作:
- 若 ,表示进行一次纵向切割,给定整数 (),沿着直线 切割。
- 若 ,表示进行一次横向切割,给定整数 (),沿着直线 切割。
保证八千代绝对不会在同一个位置切割两次(即所有的切割直线均互不相同)。
输出格式
输出共 行,每行包含一个整数,第 行的整数表示在第 次切割之后,所有小矩形中面积的最大值。
5 3 3
1 1
1 4
2 2
12
9
6
提示
:::align{center}

图 1:样例解释 :::