AT_agc031_e.[AGC031E] Snuke the Phantom Thief

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

某博物馆展出了宝石 $1, 2, \ldots, N$ 。宝石 $i$ 的位置为 $(x_i, y_i)$ ，价值为 $v_i$ （可以将博物馆看作一个二维平面）。

怪盗すぬけ计划偷取若干宝石。

偷取宝石的方式需要满足 $1, 2, \ldots, M$ 条条件，若有任一条件不满足，则会被侦探抓住。每条条件属于以下四种之一：

( $t_i$ = L, $a_i$ , $b_i$ )：被偷的宝石中， $x$ 坐标不大于 $a_i$ 的宝石数量不超过 $b_i$ 。
( $t_i$ = R, $a_i$ , $b_i$ )：被偷的宝石中， $x$ 坐标不小于 $a_i$ 的宝石数量不超过 $b_i$ 。
( $t_i$ = D, $a_i$ , $b_i$ )：被偷的宝石中， $y$ 坐标不大于 $a_i$ 的宝石数量不超过 $b_i$ 。
( $t_i$ = U, $a_i$ , $b_i$ )：被偷的宝石中， $y$ 坐标不小于 $a_i$ 的宝石数量不超过 $b_i$ 。

请你求出怪盗すぬけ能够偷取的宝石的最大总价值。

输入格式

输入按以下格式从标准输入读入。

$N$ $x_1$ $y_1$ $v_1$ $x_2$ $y_2$ $v_2$ $\ldots$ $x_N$ $y_N$ $v_N$ $M$ $t_1$ $a_1$ $b_1$ $t_2$ $a_2$ $b_2$ $\ldots$ $t_M$ $a_M$ $b_M$

输出格式

输出怪盗すぬけ能够偷取的宝石的最大总价值。

输入输出样例

输入#1

输出#1

输入#2
```
3
1 2 3
4 5 6
7 8 9
1
L 100 0
```
输出#2
```
0
```

输入#3

输出#3

输入#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

说明/提示

限制条件

$1 \leq N \leq 80$
$1 \leq x_i, y_i \leq 100$
$1 \leq v_i \leq 10^{15}$
$1 \leq M \leq 320$
$t_i$ 为 L、R、U、D 之一
$1 \leq a_i \leq 100$
$0 \leq b_i \leq N-1$
$(x_i, y_i)$ 互不相同
$(t_i, a_i)$ 互不相同
$(t_i, b_i)$ 互不相同

样例解释 1

如果偷取宝石 $1, 5, 6, 7$ ，则总价值为 $36$ 。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页