#include <bits/stdc++.h>
#define int long long
using namespace std;
//#define LOCAL
#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
#include "fish.h"
#endif
const int nmax = 3005,inf = (1LL << 60);
int n,m,x[nmax],y[nmax],w[nmax],dp[nmax][nmax][2],a[nmax][nmax];
int sum(int x, int y1, int y2) {
if (y1 > y2) {
return 0;
}
return a[y2][x] - a[y1 - 1][x] - a[y2][x - 1] + a[y1 - 1][x - 1];
}
long long solve() {
for (int i = 0; i < nmax; i++) {
for (int j = 0; j < nmax; j++) {
for (int k = 0; k <= 1; k++) {
dp[i][j][k] = -inf;
}
}
}
for (int i = 1; i <= m; i++) {
a[y[i]][x[i]] = w[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cout << a[i][j] << " ";
}
cout << "\n";
}
cout << "\n";
dp[0][0][1] = 0; /// 1 -> increasing >= , 0 -> decreasing <
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) {
for (int prev_j = 0; prev_j <= n; prev_j++) {
for (int k = 0; k <= 1; k++) {
if ( (k == 0 && j >= prev_j) || (k == 1 && j < prev_j) ) continue;
int extra = 0;
if (k == 1) {
extra += sum(i - 1, prev_j + 1, j);
} else {
extra += sum(i , j + 1, prev_j);
}
dp[i][j][k] = max(dp[i][j][k] , extra + dp[i - 1][prev_j][k]);
if (k == 0) {
dp[i][j][k] = max(dp[i][j][k] , extra + dp[i - 1][prev_j][1]);
}
}
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
for (int k = 0; k <= 1; k++) {
cout << "i = " << i << " j = " << j << " k = " << k << ": " << dp[i][j][k] << " ";
}cout << "\n";
}cout << "\n";
}
int sol = 0;
for (int i = 1; i <= n; i++) {
sol = max(sol , dp[n][i][0]);
sol = max(sol , dp[n][i][1]);
}
return sol;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
m = M;
for (int i = 0; i < m; i++) {
x[i + 1] = X[i] + 1;
y[i + 1] = Y[i] + 1;
w[i + 1] = W[i];
}
return solve();
}
#ifdef LOCAL
int32_t main() {
int n,m;
in >> n >> m;
vector<int> x(m),y(m),w(m);
for (int i = 0; i < m; i++) {
in >> x[i] >> y[i] >> w[i];
}
out << max_weights(n,m,x,y,w) << "\n";
}
#endif
Compilation message
/usr/bin/ld: /tmp/cczYGdHB.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
