#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
int order[N * 3];
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;
long long g1 = calc(h, i - 1), g2 = calc(h, i), g3 = calc(h, i + 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 * g1 + x3 * g3 - (x1 > 0) * g2);
}
}
}
}
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;
}
main() {
cin.tie(0)->sync_with_stdio(0);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
freopen("ac.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);
}
Compilation message
fish.cpp:66:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
66 | main() {
| ^~~~
fish.cpp: In function 'int main()':
fish.cpp:69:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | freopen("task.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:70:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
70 | freopen("ac.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccJB7slp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccaXbamn.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
