# 某岛

… : "…アッカリ～ン . .. . " .. .
June 25, 2023

# CodeTON Round 5

## Problem E. Tenzing and Triangle

```#include <lastweapon/io>
#include <lastweapon/fenwicktree>
using namespace lastweapon;

const int N = int(2e5) + 9;
int n, k, A; vector<PII> P[N]; LL f[N];

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n,k,A); LL z = 0;
REP(i ,n) {
int x, y, c; RD(x, y, c);
z += c; P[k-x].PB({y, c});
}

fenwick_tree<int> T(k+1);

REP(i, k+1) {
for (auto p: P[i]) T.add(p.fi, p.se);
checkMax(f[i], (LL)T.sum(0, i+1) - A*i);
REP(j, i) checkMax(f[i], f[j] + T.sum(j+1, i+1) - A*(i-j-1));
}

cout << z - f[k] << endl;
}
```

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e5) + 9;
const int NN = 4*N;
int n, k, A; vector<PII> P[N]; int f[N];

struct SegTree {
#define lx (x<<1)
#define rx (lx|1)
#define ml ((l+r)>>1)
#define mr (ml+1)
#define lc lx,l,ml
#define rc rx,mr,r
#define rt 1,0,k

int T[NN], D[NN];

void add(int x, int d) {
D[x] += d;
T[x] += d;
}
void rls(int x) {
//return;
if (D[x]) {
D[x] = 0;
}
}
void upd(int x) {
T[x] = max(T[lx], T[rx]);
}
void Build(int x, int l, int r) {
if (l == r) {
T[x] = A*l;
} else {
Build(lc);
Build(rc);
upd(x);
}
}

int Add(int x, int l, int r, const int p, const int d) {
if (l == r) {
T[x] += d;
} else {
rls(x);
if (p < mr) Add(lc, p, d);
upd(x);
}
}

void Add(int x, int l, int r, const int a, const int b, const int d) {
if (b < l || r < a) return;
if (a <= l && r <= b) {
} else {
rls(x);
upd(x);
}
}

int Query(int x, int l, int r, const int a, const int b) {
if (b < l || r < a) return 0;
if (a <= l && r <= b) {
return T[x];
} else {
rls(x);
return max(Query(lc, a, b), Query(rc, a, b));
}
}
} T;

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

RD(n,k,A); int z = 0; REP(i, n) {
int x, y, c; RD(x, y, c); z += c;
P[k-x].PB({y, c});
}

T.Build(rt);

REP(i, k+1) {