BARICAVN - BARICA
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 300000 + 5, XY = 100000 + 5, INF = 1000000000;
struct plant {
int x, y, f, id;
bool operator < (const plant &o) const {
return x < o.x || x == o.x && y < o.y;
}
} p[N];
int n, k, maxX[XY], maxY[XY], f[N];
void enter() {
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i) {
scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].f);
p[i].id = i;
}
}
void solve() {
sort(p+1, p+n+1); f[0] = -INF;
for(int i = 1; i <= n; ++i) {
int id = p[i].id;
f[id] = -INF; if(id == 1) f[id] = p[i].f;
int xx = maxX[p[i].x], yy = maxY[p[i].y];
if(f[xx] >= k && f[xx] - k + p[i].f > f[id]) f[id] = f[xx] - k + p[i].f;
if(f[yy] >= k && f[yy] - k + p[i].f > f[id]) f[id] = f[yy] - k + p[i].f;
if(f[id] > f[xx]) maxX[p[i].x] = id;
if(f[id] > f[yy]) maxY[p[i].y] = id;
}
printf("%d\n", f[n]);
}
int main() {
enter();
solve();
return 0;
}