最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 观看烟花很有趣

    正文概述 陈老师   2026-01-20 15:15:55  

    题目描述

    一个节日将在城镇的主街道上举行。主街道被划分为 nn 个区域,这些区域从左到右依次编号为 11 到 nn。相邻区域之间的距离为 11 单位长度。

    节日期间将发射 mm 个烟花。第 ii 次(1≤i≤m1 \leq i \leq m)发射将在时间 tit_{i} 于区域 aia_{i} 进行。如果你在第 ii 次发射时位于区域 xx(1≤x≤n1 \leq x \leq n),你将获得幸福值 bi−∣ai−x∣b_{i} - |a_{i} - x|(注意幸福值可能为负数)。

    你可以在单位时间间隔内移动最多 dd 单位长度,但禁止移动到主街道之外。你可以在初始时刻(时间等于 11 时)处于任意位置,目标是最大化观看烟花获得的总幸福值。求可能的最大总幸福值。

    注意多个烟花可能在同一时间发射。

    输入格式

    第一行包含三个整数 nn、mm、dd(1≤n≤1500001 \leq n \leq 150000;1≤m≤3001 \leq m \leq 300;1≤d≤n1 \leq d \leq n)。

    接下来 mm 行,每行包含三个整数 aia_{i}、bib_{i}、tit_{i}(1≤ai≤n1 \leq a_{i} \leq n;1≤bi≤1091 \leq b_{i} \leq 10^{9};1≤ti≤1091 \leq t_{i} \leq 10^{9})。第 ii 行描述第 ii 次发射的信息。

    保证满足 ti≤ti+1t_{i} \leq t_{i+1}(1≤i<m1 \leq i \lt m)的条件。

    输出格式

    输出一个整数——观看所有烟花所能获得的最大幸福值总和。

    50 3 1
    49 1 1
    26 1 4
    6 1 10
    
    -31
    
    10 2 1
    1 1000 4
    9 1000 4
    
    1992
    
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 观看烟花很有趣