#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int long long
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
int mask = 0, mx = 0;
for(int i=0; i<M; i++) mask |= (1 << (X[i] % 2));
for(int i=0; i<M; i++) mx = max(mx, Y[i]);
if(mask == 1) {
ll ans = 0;
for(int &x : W) ans += x;
return ans;
}
if(mx == 0) {
vector<ll> val(N+5), dp(N+5);
for(int i=0; i<M; i++) val[X[i]] = W[i];
ll ans = 0;
vector<ll> MX(N+5); MX[0] = val[1];
for(int i=1; i<N; i++) {
dp[i] = max(dp[i-1], val[i-1]);
if(i >= 3) dp[i] = max(dp[i], MX[i-3] + val[i-1]);
if(i >= 2) dp[i] = max(dp[i], dp[i-2] + val[i-1]);
MX[i] = max(MX[i-1], dp[i] + val[i+1]);
}
for(int i=0; i<N; i++) ans = max(ans, dp[i] + val[i+1]);
return ans;
}
if(mx <= 8) {
ll val[N+5][mx+5], dp[N+5][mx+5][mx+5];
memset(val, 0, sizeof(val)); memset(dp, 0, sizeof(dp));
for(int i=0; i<M; i++) val[X[i]][Y[i]] = W[i];
for(int i=0; i<N; i++)
for(int j=1; j<=mx; j++) val[i][j] += val[i][j-1];
for(int j=0; j<=mx+1; j++) {
for(int k=0; k<=mx+1; k++) {
if(j > k) dp[1][j][k] = val[0][j-1] - (k ? val[0][k-1] : 0);
else if(j < k) dp[1][j][k] = val[1][k-1] - (j ? val[1][j-1] : 0);
}
}
for(int i=2; i<N; i++) {
for(int j=0; j<=mx+1; j++) {
for(int k=0; k<=mx+1; k++) {
if(j > k) dp[i][j][k] = (j ? val[i-1][j-1] : 0) - (k ? val[i-1][k-1] : 0);
if(j < k) dp[i][j][k] = (k ? val[i][k-1] : 0) - (j ? val[i][j-1] : 0);
if(k) dp[i][j][k] += val[i-2][k-1];
for(int l=0; l<=mx+1; l++) {
if(l <= k && k <= j) {
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] + (j ? val[i-1][j-1] : 0) - (k ? val[i-1][k-1] : 0));
}
if(l >= k && k >= j) {
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] + (k ? val[i][k-1] : 0) - (j ? val[i][j-1] : 0));
}
if(l <= k && k >= j) {
dp[i][j][k] = max(dp[i][j][k], dp[i-1][k][l] + (k ? val[i][k-1] : 0) - (j ? val[i][j-1] : 0));
}
}
}
}
}
ll ans = 0;
// // cout << dp[3][3][2] << '\n';
// for(int i=0; i<N; i++) {
// for(int j=0; j<=mx+1; j++) {
// for(int k=0; k<=mx+1; k++) {
// cout << i << " " << j << " " << k << ": " << dp[i][j][k] << '\n';
// }
// }
// }
for(int i=0; i<N; i++)
for(int j=0; j<=mx+1; j++)
for(int k=0; k<=mx+1; k++) ans = max(ans, dp[i][j][k] + val[i+1][j]);
return ans;
}
return 0;
}
Compilation message
/usr/bin/ld: /tmp/cc2dyidw.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
