#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MXN = 2e5 + 5;
long long mx[MXN];
vector<long long> lft[MXN], rig[MXN], in[MXN];
vector<long long> pre[2][MXN], suf[2][MXN];
vector<long long> dp[2][MXN];
vector<long long> ind[MXN];
vector<array<long long, 2>> val[MXN];
/*
0 = len[i] < len[i + 1];
1 = len[i] > len[i + 1];
*/
long long max_weights(int32_t N, int32_t M, vector<int32_t> X, vector<int32_t> Y, vector<int32_t> W)
{
for (int i = 0; i < M; i++)
{
if (X[i] >= 1) ind[X[i]].push_back(Y[i] + 1);
if (X[i] + 2 <= N) ind[X[i] + 2].push_back(Y[i] + 1);
val[X[i] + 1].push_back({Y[i] + 1, W[i]});
}
for (int i = 1; i <= N; i++) sort(ind[i].begin(), ind[i].end());
for (int i = 1; i <= N; i++)
{
int k1 = 0, k2 = 0, k3 = 0;
for (int j = 0; j < ind[i].size(); j++)
{
lft[i].push_back((lft[i].empty() ? 0 : lft[i].back()));
rig[i].push_back((rig[i].empty() ? 0 : rig[i].back()));
in[i].push_back((in[i].empty() ? 0 : in[i].back()));
while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
}
}
for (int i = 1; i <= N; i++)
{
int k1 = 0, k2 = 0, k3 = 0, k4 = 0;
for (int j = 0; j < ind[i].size(); j++)
{
dp[0][i].push_back(lft[i][j] + rig[i][j]);
dp[1][i].push_back(lft[i][j] + rig[i][j]);
if (i <= 1) continue;
while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
if (k1 - 1 >= 0) dp[0][i][j] = max(dp[0][i][j], pre[0][i - 1][k1 - 1] + (lft[i][j] + rig[i][j]));
if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
if (i <= 2) continue;
while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
long long A = (k3 - 1 >= 0 ? pre[1][i - 2][k3 - 1] : 0) + lft[i][j] + rig[i][j];
long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
dp[0][i][j] = max({dp[0][i][j], A, B});
dp[1][i][j] = max({dp[1][i][j], A, B});
if (i <= 3) continue;
dp[0][i][j] = max(dp[0][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
dp[1][i][j] = max(dp[1][i][j], mx[i - 3] + lft[i][j] + rig[i][j]);
}
for (int j = 0; j < ind[i].size(); j++)
{
dp[1][i][j] = max(dp[1][i][j], dp[0][i][j]);
mx[i] = max({mx[i], dp[0][i][j], dp[1][i][j]});
}
for (int j = 0; j < ind[i].size(); j++)
{
pre[0][i].push_back(max((pre[0][i].empty() ? 0 : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
pre[1][i].push_back(max((pre[1][i].empty() ? 0 : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
}
for (int j = (int)ind[i].size() - 1; j >= 0; j--)
{
suf[0][i].push_back(max((suf[0][i].empty() ? 0 : suf[0][i].back()), dp[1][i][j]));
suf[1][i].push_back(max((suf[1][i].empty() ? 0 : suf[0][i].back()), max(dp[0][i][j], dp[1][i][j])));
}
reverse(suf[0][i].begin(), suf[0][i].end());
reverse(suf[1][i].begin(), suf[1][i].end());
}
long long ans = 0;
for (int i = 1; i <= N; i++)
{
for (long long &j : dp[0][i]) ans = max(ans, j);
for (long long &j : dp[1][i]) ans = max(ans, j);
}
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int32_t, int32_t, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:34:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | while (k1 < val[i - 1].size() && val[i - 1][k1][0] <= ind[i][j]) lft[i][j] += val[i - 1][k1][1], k1++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:40:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | while (k2 < val[i + 1].size() && val[i + 1][k2][0] <= ind[i][j]) rig[i][j] += val[i + 1][k2][1], k2++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:41:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
41 | while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
| ~~~^~~~~~~~~~~~~~~
fish.cpp:47:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:52:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:53:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:55:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | if (k2 < ind[i - 1].size()) dp[1][i][j] = max(dp[1][i][j], suf[0][i - 1][k2] + (rig[i][j] - in[i][j]));
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:57:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:58:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:60:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:67:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:72:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
63940 KB |
Output is correct |
| 2 |
Correct |
33 ms |
65984 KB |
Output is correct |
| 3 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 4 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 5 |
Incorrect |
113 ms |
116352 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572' |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
7 ms |
52056 KB |
Output is correct |
| 2 |
Incorrect |
62 ms |
82008 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '56379036510698' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
51896 KB |
Output is correct |
| 3 |
Incorrect |
48 ms |
73996 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 3 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 4 |
Correct |
7 ms |
52116 KB |
Output is correct |
| 5 |
Correct |
7 ms |
52312 KB |
Output is correct |
| 6 |
Correct |
7 ms |
51912 KB |
Output is correct |
| 7 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 8 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219939902278' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 3 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 4 |
Correct |
7 ms |
52116 KB |
Output is correct |
| 5 |
Correct |
7 ms |
52312 KB |
Output is correct |
| 6 |
Correct |
7 ms |
51912 KB |
Output is correct |
| 7 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 8 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219939902278' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 3 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 4 |
Correct |
7 ms |
52116 KB |
Output is correct |
| 5 |
Correct |
7 ms |
52312 KB |
Output is correct |
| 6 |
Correct |
7 ms |
51912 KB |
Output is correct |
| 7 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 8 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 9 |
Incorrect |
8 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '219939902278' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
52060 KB |
Output is correct |
| 2 |
Correct |
7 ms |
51896 KB |
Output is correct |
| 3 |
Incorrect |
48 ms |
73996 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '369591758422' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
28 ms |
63940 KB |
Output is correct |
| 2 |
Correct |
33 ms |
65984 KB |
Output is correct |
| 3 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 4 |
Correct |
7 ms |
52060 KB |
Output is correct |
| 5 |
Incorrect |
113 ms |
116352 KB |
1st lines differ - on the 1st token, expected: '149814460735479', found: '44945481875572' |
| 6 |
Halted |
0 ms |
0 KB |
- |
