#include "fish.h"
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
ll solve(vector<vector<pair<int, ll>>> &fish, int n)
{
ll res = 0;
vector<vector<ll>> dp0(fish.size()), dp1(fish.size());
for (int i = 0; i < fish.size(); ++i)
{
fish[i].emplace_back(n, 0);
dp0[i].resize(fish[i].size());
ll mx = 0;
if (i != 0)
{
for (int j = 0; j < fish[i - 1].size(); ++j)
{
mx = max(mx, dp1[i - 1][j]);
}
fill(dp0[i].begin(), dp0[i].end(), mx);
mx = 0;
}
for (int j = 0, k = 0; j < fish[i].size(); ++j)
{
if (i != 0)
{
while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
{
mx = max(mx, dp0[i - 1][k]);
mx += fish[i - 1][k].second;
++k;
}
}
dp0[i][j] = max(mx, dp0[i][j]);
}
dp0 = dp1;
if (i != 0)
{
ll mx = 0;
for (int j = (int)fish[i].size() - 1, k = (int)fish[i - 1].size() - 1; j >= 0; --j)
{
while (k >= 0 && fish[i - 1][k].first > fish[i][j].first)
{
mx = max(mx, dp1[i - 1][k]);
--k;
}
mx += fish[i][j].second;
dp1[i][j] = max(dp1[i][j], mx);
res = max(dp1[i][j], res);
}
}
}
return res;
}
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W)
{
vector<tuple<int, int, ll>> xyw(m);
for (int i = 0; i < m; ++i) xyw[i] = {X[i], Y[i], W[i]};
sort(xyw.begin(), xyw.end());
ll res = 0;
vector<vector<pair<int, ll>>> tos;
int prevX = -1;
for (auto [x, y, w] : xyw)
{
if (x > prevX + 1)
{
tos.push_back(vector<pair<int, ll>>());
res += solve(tos, n);
tos.clear();
tos.push_back(vector<pair<int, ll>>());
prevX = x - 1;
}
if (x == prevX + 1)
{
tos.push_back(vector<pair<int, ll>>());
}
tos.back().emplace_back(y, w);
prevX = x;
}
if (prevX != n - 1) tos.push_back(vector<pair<int, ll>>());
res += solve(tos, n);
return res;
}
Compilation message
fish.cpp: In function 'll solve(std::vector<std::vector<std::pair<int, long long int> > >&, int)':
fish.cpp:14:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
14 | for (int i = 0; i < fish.size(); ++i)
| ~~^~~~~~~~~~~~~
fish.cpp:21:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int j = 0; j < fish[i - 1].size(); ++j)
| ~~^~~~~~~~~~~~~~~~~~~~
fish.cpp:28:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
28 | for (int j = 0, k = 0; j < fish[i].size(); ++j)
| ~~^~~~~~~~~~~~~~~~
fish.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | while (k < fish[i - 1].size() && fish[i - 1][k].first < fish[i][j].first)
| ~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
10564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
340 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
35 ms |
10564 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
