P1502 窗口的星星

    • 464通过
    • 1.9K提交
  • 题目提供者 cyrcyr
  • 评测方式 云端评测
  • 标签 离散化 线段树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    小卡买到了一套新房子,他十分的高兴,在房间里转来转去。

    题目描述

    晚上,小卡从阳台望出去,“哇~~~~好多星星啊”,但他还没给其他房间设一个窗户,天真的小卡总是希望能够在晚上能看到最多最亮的星星,但是窗子的大小是固定的,边也必须和地面平行。这时小卡使用了超能力(透视术)知道了墙后面每个星星的位置和亮度,但是小卡发动超能力后就很疲劳,只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

    输入输出格式

    输入格式:

    本题有多组数据,第一行为T 表示有T组数据T<=10

    对于每组数据

    第一行3个整数n,W,H,(n<=10000,1<=W,H<=1000000)表示有n颗星星,窗口宽为W,高为H。

    接下来n行,每行三个整数xi,yi,li 表示星星的坐标在(xi,yi),亮度为li。(0<=xi,yi<2^31)

    输出格式:

    T个整数,表示每组数据中窗口星星亮度总和的最大值。

    输入输出样例

    输入样例#1: 复制
    2
    3 5 4
    1 2 3
    2 3 2
    6 3 1
    3 5 4
    1 2 3
    2 3 2
    5 3 1
    
    输出样例#1: 复制
    5
    6
    

    说明

    小卡买的窗户框是金属做的,所以在边框上的不算在内。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。