#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<pair<int, ll>>P[N];
for (int i = 0; i < M; i++)
P[X[i]].push_back({Y[i], W[i]});
for (int i = 0; i < N; i++)
sort(P[i].begin(), P[i].end());
for (int i = 0; i < N; i++)
{
P[i].push_back({N, 0});
for (int j = 1; j < (int)P[i].size(); j++)
P[i][j].second += P[i][j - 1].second;
}
int ret = 0;
ll dp[N];
ll u[N][N];
ll d[N][N];
ll u1[N][N];
ll d1[N][N];
auto get = [&](int x, int y)->ll
{
if (x < 0 || x >= N)
return 0;
auto it = lower_bound(P[x].begin(), P[x].end(), make_pair(y + 1, -1ll));
if (it == P[x].begin())
return 0;
it--;
return it->second;
};
for (int x = 0; x < N; x++)
{
dp[x] = 0;
for (int y = 0; y < N; y++)
{
u[x][y] = d[x][y] = 0;
u1[x][y] = u[x][y] - get(x, y);
d1[x][y] = d[x][y] + get(x + 1, y);
}
ll sum = 0;
int i = 0;
if (x == 0)
continue;
for (int y = 0; y < N; y++)
{
u[x][y] = dp[x - 1];
u[x][y] = max(u[x][y], get(x - 1, y) + (x - 2 >= 0 ? dp[x - 2] : 0ll));
u[x][y] -= get(x - 1, y);
for (int y1 = 0; y1 <= y; y1++)
u[x][y] = max(u[x][y], u1[x - 1][y1]);
u[x][y] += get(x - 1, y);
}
for (int y = 0; y < N; y++)
u1[x][y] = u[x][y] - get(x, y);
d[x][N - 1] = u[x][N - 1];
for (int y = N - 1; y >= 0; y--)
{
d[x][y] += get(x, y);
for (int y1 = y; y1 < N; y1++)
d[x][y] = max(d[x][y], d1[x - 1][y1]);
d[x][y] -= get(x, y);
}
for (int y = N - 1; y >= 0; y--)
d1[x][y] = d[x][y] + get(x + 1, y);
dp[x] = dp[x - 1];
dp[x] = max(dp[x], get(x, N - 1) + u[x - 1][N - 1]);
dp[x] = max(dp[x], u[x][N - 1]);
for (int y = 0; y < N; y++)
{
dp[x] = max(dp[x], d1[x - 1][y]);
dp[x] = max(dp[x], d[x][y]);
}
}
return dp[N - 1];
}
int main()
{
cout << max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3}) << endl;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:44:12: warning: unused variable 'sum' [-Wunused-variable]
44 | ll sum = 0;
| ^~~
fish.cpp:45:13: warning: unused variable 'i' [-Wunused-variable]
45 | int i = 0;
| ^
fish.cpp:19:9: warning: unused variable 'ret' [-Wunused-variable]
19 | int ret = 0;
| ^~~
/usr/bin/ld: /tmp/ccm8IOhP.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc0tdW2Q.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
