← 返回题目列表

Codeforces · 241/C

C. 镜盒

中文机器翻译题面 查看原题

Mirror Box 是伊朗国家游乐园 (INAP) 中一款流行游戏的名称。本游戏中有一个木箱,长105厘米,高100厘米。盒子的天花板和地板的某些部分被镜子覆盖。盒子的相对两侧有两个可以忽略不计的小孔,高度分别为 hl 和 hr 厘米(距地板)。下图显示了盒子的样子。

游戏中会给你一把激光枪,可以射击一次。激光束必须从一个孔进入并从另一个孔退出。每个镜子都有一个预设的数字 vi,它显示了玩家的激光束击中该镜子时获得的分数。另外,为了让事情变得更有趣,光束不能多次击中任何镜子。

给定有关盒子的信息,您的任务是找到玩家可能获得的最大分数。请注意,反射遵循“入射角等于反射角”的定律。

输入

输入的第一行包含三个空格分隔的整数 hl, hr, n (0 < hl, hr < 100, 0 ≤ n ≤ 100) — 孔的高度和镜子的数量。

接下来的 n 行包含镜子的描述。第 i 行包含空格分隔的 vi、ci、ai、bi;整数 vi (1 ≤ vi ≤ 1000) 是第 i 个镜像的得分;字符 ci 表示第 i 个镜子的位置 - 如果 ci 等于“T”,则镜子位于天花板上;如果 ci 等于“F”,则镜子位于地板上;整数ai 和bi (0 ≤ ai < bi ≤ 105) 表示镜像起点和终点的x 坐标。

没有两个镜子会共享一个公共点。考虑到 x 坐标从左向右增加,因此具有高度为 hl 的孔的边界的 x 坐标等于 0,而具有高度为 hr 的孔的边界的 x 坐标等于 105。

输出

唯一的输出行应包含一个整数 - 玩家可以获得的最大可能得分。

示例

输入 #1

50 50 7
10 F 1 80000
20 T 1 80000
30 T 81000 82000
40 T 83000 84000
50 T 85000 86000
60 T 87000 88000
70 F 81000 89000

输出 #1

100

输入 #2

80 72 9
15 T 8210 15679
10 F 11940 22399
50 T 30600 44789
50 F 32090 36579
5 F 45520 48519
120 F 49250 55229
8 F 59700 80609
35 T 61940 64939
2 T 92540 97769

输出 #2

120

注意

第二个示例如上所示。红色光束获得 10 + 50 + 5 + 35 + 8 + 2 = 110 分,蓝色光束获得 120 分。

声明中给出的图片上的红色光束显示了激光束如何大致移动,这只是说明激光束如何获得分数。因此,对于第二个样本,不存在得分为 110 的光束。