A4856 | [NOIP2023] 天天爱打卡
来源NOIP提高组 / 2023
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。
开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。
对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的**能量值可以是负数**。
而且大 Y 不会**连续**跑步打卡**超过** $k$ 天；即不能存在 $1\le x\le n-k$，使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。
小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1\le i \le m$）个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。
现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值**最高**可以达到多少？
开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 $n$ 天，编号为从 $1$ 到 $n$。
对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 $d$。初始时，他的能量值是 $0$，并且试运行期间他的**能量值可以是负数**。
而且大 Y 不会**连续**跑步打卡**超过** $k$ 天；即不能存在 $1\le x\le n-k$，使得他在第 $x$ 到第 $x+k$ 天均进行了跑步打卡。
小 T 同学在软件中设计了 $m$ 个挑战，第 $i$（$1\le i \le m$）个挑战可以用三个正整数 $(x_i,y_i,v_i)$ 描述，表示如果在第 $x_i$ 天时，用户已经连续跑步打卡至少 $y_i$ 天（即第 $x_i-y_i+1$ 到第 $x_i$ 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 $v_i$。
现在大 Y 想知道，在软件试运行的 $n$ 天结束后，他的能量值**最高**可以达到多少？
输入格式
**本题的测试点包含有多组测试数据。**
输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。
接下来，对于每组测试数据：
- 输入的第一行包含四个正整数 $n,m,k,d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
- 接下来 $m$ 行，每行包含三个正整数 $x_i,y_i,v_i$，表示一次挑战。
输入的第一行包含两个整数 $c$ 和 $t$，分别表示测试点编号和测试数据组数。对于样例，$c$ 表示该样例与测试点 $c$ 拥有相同的限制条件。
接下来，对于每组测试数据：
- 输入的第一行包含四个正整数 $n,m,k,d$，分别表示试运行的天数、挑战的个数、大 Y 单次跑步打卡的连续天数限制以及大 Y 跑步打卡减少的能量值。
- 接下来 $m$ 行，每行包含三个正整数 $x_i,y_i,v_i$，表示一次挑战。
输出格式
输出一行一个整数表示对应的答案。
输入输出样例
输入 #1
1 1 3 2 2 1 2 2 4 3 2 3
输出 #1
2
**【样例解释 #1】**
在第 $1,2$ 天跑步打卡，第 $3$ 天不跑步打卡，最终会获得 $(-1)+(-1)+4=2$ 的能量值。
**【样例解释 #2】**
该组样例满足测试点 $3$ 的条件。
**【样例解释 #3】**
该组样例满足测试点 $5$ 的条件。
**【样例解释 #4】**
该组样例满足测试点 $15$ 的条件。
**【样例解释 #5】**
该组样例满足测试点 $17$ 的条件。
**【样例解释 #6】**
该组样例满足测试点 $19$ 的条件。
**【数据范围】**
记 $l_i=x_i-y_i+1$，$r_i=x_i$；
对于所有测试数据，保证：$1\le t\le 10$，$1\le k\le n\le 10^9$，$1\le m\le 10^5$，$1\le l_i\le r_i\le n$，$1\le d,v_i\le 10^9$。
|测试点编号|$n \le$|$m \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1, 2$|$18$|$10 ^ 2$|无|
|$3, 4$|$10 ^ 2$|$10 ^ 2$|无|
|$5 \sim 7$|$10 ^ 3$|$10 ^ 3$|无|
|$8, 9$|$10 ^ 3$|$10 ^ 5$|无|
|$10, 11$|$10 ^ 5$|$10 ^ 3$|无|
|$12 \sim 14$|$10 ^ 5$|$10 ^ 5$|无|
|$15, 16$|$10 ^ 9$|$10 ^ 5$|A|
|$17, 18$|$10 ^ 9$|$10 ^ 5$|B|
|$19 \sim 21$|$10 ^ 9$|$10 ^ 5$|C|
|$22 \sim 25$|$10 ^ 9$|$10 ^ 5$|无|
特殊性质 A：$k\le 10^2$；
特殊性质 B：$\forall 1\le i<m$，$r_i<l_{i+1}$；
特殊性质 C：$\forall 1\le i<j\le m$，$l_i<l_j$，$r_i<r_j$。
在第 $1,2$ 天跑步打卡，第 $3$ 天不跑步打卡，最终会获得 $(-1)+(-1)+4=2$ 的能量值。
**【样例解释 #2】**
该组样例满足测试点 $3$ 的条件。
**【样例解释 #3】**
该组样例满足测试点 $5$ 的条件。
**【样例解释 #4】**
该组样例满足测试点 $15$ 的条件。
**【样例解释 #5】**
该组样例满足测试点 $17$ 的条件。
**【样例解释 #6】**
该组样例满足测试点 $19$ 的条件。
**【数据范围】**
记 $l_i=x_i-y_i+1$，$r_i=x_i$；
对于所有测试数据，保证：$1\le t\le 10$，$1\le k\le n\le 10^9$，$1\le m\le 10^5$，$1\le l_i\le r_i\le n$，$1\le d,v_i\le 10^9$。
|测试点编号|$n \le$|$m \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1, 2$|$18$|$10 ^ 2$|无|
|$3, 4$|$10 ^ 2$|$10 ^ 2$|无|
|$5 \sim 7$|$10 ^ 3$|$10 ^ 3$|无|
|$8, 9$|$10 ^ 3$|$10 ^ 5$|无|
|$10, 11$|$10 ^ 5$|$10 ^ 3$|无|
|$12 \sim 14$|$10 ^ 5$|$10 ^ 5$|无|
|$15, 16$|$10 ^ 9$|$10 ^ 5$|A|
|$17, 18$|$10 ^ 9$|$10 ^ 5$|B|
|$19 \sim 21$|$10 ^ 9$|$10 ^ 5$|C|
|$22 \sim 25$|$10 ^ 9$|$10 ^ 5$|无|
特殊性质 A：$k\le 10^2$；
特殊性质 B：$\forall 1\le i<m$，$r_i<l_{i+1}$；
特殊性质 C：$\forall 1\le i<j\le m$，$l_i<l_j$，$r_i<r_j$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？