#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
#define int long long
using namespace std;
const int N = 3e5 + 10;
int order[N];
vector<int> fish[N];
vector<long long> pref[N];
long long f[3][2][2][2];
long long calc(int h, int col) {
if (h == -1 || col < 0 || fish[col].empty()) return 0;
int idx = --upper_bound(fish[col].begin(), fish[col].end(), h) - fish[col].begin();
return pref[col][idx];
}
long long max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < n; i++) fish[i].push_back(0), pref[i].push_back(0);
for(int i = 0; i < m; i++) order[i] = i;
sort(order, order + m, [&] (const int &A, const int &B) {
return Y[A] < Y[B];
});
for(int cur = 0; cur < m; cur++) {
int i = order[cur];
fish[X[i]].push_back(Y[i]);
pref[X[i]].push_back(pref[X[i]].back() + W[i]);
}
for(int i = 0; i < n; i++) fish[i].push_back(n + 1);
bool pre = 0;
memset(f, -61, sizeof(f));
f[0][0][0][0] = 0;
for(int i = 0; i < n; i++) {
bool cur = pre ^ 1;
for(int &preh : fish[i]) {
int h = preh - 1;
for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) {
for(int y1 = 0; y1 < 3; y1++) for(int y2 = 0; y2 < 2; y2++) for(int y3 = 0; y3 < 2; y3++) {
bool ok = 1;
if (x2) ok &= y1 == 2;
if (y3) ok &= x1 == 1;
if (ok) {
f[x1][x2][x3][cur] = max(f[x1][x2][x3][cur], f[y1][y2][y3][pre] + x2 * calc(h, i - 1) + x3 * calc(h, i + 1) - (x1 > 0) * calc(h, i));
}
}
}
}
for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) f[x1][x2][x3][pre] = -1e18;
pre = cur;
}
long long res = 0;
for(int x1 = 0; x1 < 3; x1++) for(int x2 = 0; x2 < 2; x2++) for(int x3 = 0; x3 < 2; x3++) {
res = max(res, f[x1][x2][x3][pre]);
}
return res;
}
#ifdef ngu
main() {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
int n, m; cin >> n >> m;
vector<int> x(m), y(m), w(m);
for(int i = 0; i < m; i++) cin >> x[i] >> y[i] >> w[i];
cout << max_weights(n, m, x, y, w);
}
#endif // ngu
Compilation message
/usr/bin/ld: /tmp/ccA21efE.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
