中文
日本語
English
| P6472幻龙偷猪 | ||
|
问题描述
何老板在农场上养了n头猪，编号1到n,其中第i头猪的坐标为(Xi,Yi),第i头猪的体重为Vi,猪们很乖，它们不会移动位置。(我们可以把农场看作二维平面)。
幻龙想要偷走一些猪。
要从何老板那里偷猪是一件非常困难的事情，有m个条件(编号1到m)需要满足，每个条件都是下面四种描述之一：
ti='L',ai,bi:幻龙最多能从x坐标小于等于ai的猪中偷走bi只；
ti='R',ai,bi:幻龙最多能从x坐标大于等于ai的猪中偷走bi只；
ti='D',ai,bi:幻龙最多能从y坐标小于等于ai的猪中偷走bi只；
ti='U',ai,bi:幻龙最多能从y坐标大于等于ai的猪中偷走bi只；
问，幻龙能偷走的猪的最大重量总和。
输入格式
第一行，一个整数n
接下来n行，每行三个整数Xi,Yi,Vi描述一头猪的信息
接下来一行，一个整数m
接下来m行，每行三个整数ti,ai,bi描述一个条件。
输出格式
一个整数，表示能偷到的最大总重
样例输入 1
7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2
样例输出 1
36
样例输入 2
3
1 2 3
4 5 6
7 8 9
1
L 100 0
样例输出 2
0
样例输入 3
4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1
样例输出 3
13
样例输入 4
10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5
样例输出 4
305223377000