| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1057406 |
2024-08-13T18:53:19 Z |
aykhn |
Catfish Farm (IOI22_fish) |
C++17 |
|
33 ms |
62000 KB |
#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];
*/
int A[8] = {0, 0, -1, -1, -1, 1, 1, 1};
int B[8] = {-1, 1, 0, -1, 1, 0, -1, 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++)
{
X[i]++, Y[i]++;
for (int j = 0; j < 8; j++)
{
int x = X[i] + A[j], y = Y[i] + B[j];
if (min(x, y) < 1 || max(x, y) > N)
{
ind[x].push_back(y);
}
}
val[X[i]].push_back({Y[i], W[i]});
}
for (int i = 1; i <= N; i++) sort(ind[i].begin(), ind[i].end()), sort(val[i].begin(), val[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() ? 0LL : lft[i].back()));
rig[i].push_back((rig[i].empty() ? 0LL : rig[i].back()));
in[i].push_back((in[i].empty() ? 0LL : 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() ? 0LL : pre[0][i].back()), dp[0][i][j] - rig[i][j] - in[i][j]));
pre[1][i].push_back(max((pre[1][i].empty() ? 0LL : pre[1][i].back()), max(dp[0][i][j], dp[1][i][j]) - rig[i][j]));
}
suf[0][i].assign(ind[i].size(), 0);
suf[1][i].assign(ind[i].size(), 0);
for (int j = (int)ind[i].size() - 1; j >= 0; j--)
{
if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
suf[0][i][j] = max(suf[0][i][j], dp[1][i][j]);
suf[1][i][j] = max(suf[1][i][j], max(dp[0][i][j], dp[1][i][j]));
}
}
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:43: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]
43 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:48: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]
48 | 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:49: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]
49 | 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:50: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]
50 | while (k3 < val[i].size() && val[i][k3][0] <= ind[i][j]) in[i][j] += val[i][k3][1], k3++;
| ~~~^~~~~~~~~~~~~~~
fish.cpp:56: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]
56 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:61: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]
61 | while (k1 < ind[i - 1].size() && ind[i - 1][k1] <= ind[i][j]) k1++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:62: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]
62 | while (k2 < ind[i - 1].size() && ind[i - 1][k2] < ind[i][j]) k2++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:64: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]
64 | 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:66: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]
66 | while (k3 < ind[i - 2].size() && ind[i - 2][k3] <= ind[i][j]) k3++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:67: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]
67 | while (k4 < ind[i - 2].size() && ind[i - 2][k4] < ind[i][j]) k4++;
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:69: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]
69 | long long B = (k4 < ind[i - 2].size() ? suf[1][i - 2][k4] : 0) + rig[i][j];
| ~~~^~~~~~~~~~~~~~~~~~~
fish.cpp:76: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]
76 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:81: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]
81 | for (int j = 0; j < ind[i].size(); j++)
| ~~^~~~~~~~~~~~~~~
fish.cpp:90: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]
90 | if (j + 1 < ind[i].size()) suf[0][i][j] = suf[0][i][j + 1], suf[1][i][j] = suf[1][i][j + 1];
| ~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
57796 KB |
Output is correct |
| 2 |
Correct |
33 ms |
62000 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
52056 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
52056 KB |
1st lines differ - on the 1st token, expected: '2', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '3', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
52060 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
57796 KB |
Output is correct |
| 2 |
Correct |
33 ms |
62000 KB |
Output is correct |
| 3 |
Incorrect |
11 ms |
52056 KB |
1st lines differ - on the 1st token, expected: '10082010', found: '0' |
| 4 |
Halted |
0 ms |
0 KB |
- |
