TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P6472
  • 問題
  • P6472幻龙偷猪
    制限 : 時間制限 : 10000 MS   メモリ制限 : 565536 KB
    審判説明 : 1s,512m
    問題説明

    何老板在农场上养了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

    ヒント
  • $ 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 $
  • $ 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) $ 不会有重复.

  • ソース  AGC031E