← 返回题目
题库练习 挖宝藏
← 上一题 下一题 →

A2537 | 挖宝藏

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

JP 不好好训练，又喜欢上了另一个游戏——寻宝。

游戏里有 $n$ 处宝藏，它们被埋在一个无限大的二维网格中。每个宝藏都有价值 $P_i$，位置是 $(x_i,y_i)$。

如果网格 $(x,y)$ 满足下面两个条件之一，则它是可挖掘的：

- $y=-1$。

- $(x-1,y+1),(x,y+1),(x+1,y+1)$ 这三个方格都已经被挖掘了。

挖掘一个方格的代价为 $1$。当一个宝藏被挖掘出来时，就认为已经获得了它的价值。请你帮 JP 求出所能得到的最大利润，也即价值减代价。（可能一个宝藏也不挖，利润为 $0$）

输入格式

第一行为 $n$，表示宝藏数量。

接下来 $n$ 行，每行三个整数 $x_i,y_i,P_i$ 表示宝藏的位置和价值。

输出格式

一行一个整数，表示最大利润。

输入输出样例

输入 #1
5
1 -1 2
0 -1 2
4 -1 1
3 -1 2
2 -1 2
输出 #1
4
C++ 编辑器
输入
输出