#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 3e5 + 2;
const long long INF = 1e18;
unordered_map<int, long long> costCell[MAX_N], dp[MAX_N], dpLower[MAX_N], spX[MAX_N], maxPref1[MAX_N], maxSuf2[MAX_N], maxPref3[MAX_N];
vector <int> ys[MAX_N];
long long max_weights( int n, int m, vector <int> X, vector <int> Y, vector <int> W ) {
for ( int i = 0; i < m; i++ ) {
X[i]++;
Y[i]++;
costCell[X[i]][Y[i]] = W[i];
ys[X[i] - 1].push_back( Y[i] );
ys[X[i] + 1].push_back( Y[i] );
}
ys[0].clear();
ys[n + 1].clear();
for ( int x = 0; x <= n + 1; x++ )
ys[x].push_back( 0 );
for ( int x = 1; x <= n; x++ ) {
sort( ys[x].begin(), ys[x].end() );
ys[x].resize( unique( ys[x].begin(), ys[x].end() ) - ys[x].begin() );
}
for ( int x = 1; x <= n; x++ ) {
vector<int> yss;
for ( int i = 0; i < ys[x].size(); i++ )
yss.push_back( ys[x][i] );
for ( int i = 0; i < ys[x - 1].size(); i++ )
yss.push_back( ys[x - 1][i] );
for ( int i = 0; i < ys[x + 1].size(); i++ )
yss.push_back( ys[x + 1][i] );
sort( yss.begin(), yss.end() );
yss.resize( unique( yss.begin(), yss.end() ) - yss.begin() );
for ( int i = 1; i < yss.size(); i++ )
spX[x][yss[i]] = spX[x][yss[i - 1]] + costCell[x][yss[i]];
}
dp[0][0] = dpLower[0][0] = 0;
for ( int x = 1; x <= n + 1; x++ ) {
int lower1 = 0, upper1 = 0, lower2 = 0, upper2 = 0;
for ( int i = 0; i < ys[x].size(); i++ ) {
int crtY = ys[x][i];
dp[x][crtY] = dpLower[x][crtY] = -INF;
if ( x >= 1 ) {
while ( lower1 + 1 < ys[x - 1].size() && ys[x - 1][lower1 + 1] <= crtY )
lower1++;
while ( upper1 < ys[x - 1].size() && ys[x - 1][upper1] < crtY )
upper1++;
if ( lower1 >= 0 ) {
int prevY = ys[x - 1][lower1];
dpLower[x][i] = max( dpLower[x][i], maxPref1[x - 1][lower1] + spX[x - 1][crtY] );
dp[x][i] = max( dp[x][i], maxPref1[x - 1][lower1] + spX[x - 1][crtY] );
}
if ( upper1 < ys[x - 1].size() ) {
int prevY = ys[x - 1][upper1];
dp[x][i] = max( dp[x][i], maxSuf2[x - 1][upper1] - spX[x][crtY] );
}
}
if ( x >= 2 ) {
while ( lower2 + 1 < ys[x - 2].size() && ys[x - 2][lower2 + 1] <= crtY )
lower2++;
while ( upper2 < ys[x - 2].size() && ys[x - 2][upper2] < crtY )
upper2++;
if ( lower2 >= 0 ) {
int prevY = ys[x - 2][lower2];
dpLower[x][i] = max( dpLower[x][i], maxPref3[x - 2][lower2] + spX[x - 1][i] );
dp[x][i] = max( dp[x][i], maxPref3[x - 2][lower2] + spX[x - 1][crtY] );
}
if ( upper2 < ys[x - 2].size() ) {
int prevY = ys[x - 2][upper2];
dpLower[x][i] = max( dpLower[x][i], maxSuf2[x - 2][upper2] );
dp[x][i] = max( dp[x][i], maxSuf2[x - 2][upper2] );
}
}
maxPref1[x][i] = dpLower[x][i] - spX[x][crtY];
maxSuf2[x][i] = dp[x][i] + spX[x + 1][crtY];
maxPref3[x][i] = dpLower[x][i];
}
for ( int i = 1; i < ys[x].size(); i++ ) {
maxPref1[x][ys[x][i]] = max( maxPref1[x][i], maxPref1[x][i - 1] );
maxPref3[x][ys[x][i]] = max( maxPref3[x][i], maxPref3[x][i - 1] );
}
for ( int i = ys[x].size() - 2; i >= 0; i-- )
maxSuf2[x][ys[x][i]] = max( maxSuf2[x][i], maxSuf2[x][i + 1] );
}
/*for ( int x = 0; x <= n + 1; x++ ) {
for ( int i = 0; i < ys[x].size(); i++ )
printf( "(%d %lld) ", ys[x][i], dp[x][i] );
printf( "\n" );
}*/
return dp[n + 1][0];
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:32:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for ( int i = 0; i < ys[x].size(); i++ )
| ~~^~~~~~~~~~~~~~
fish.cpp:34:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for ( int i = 0; i < ys[x - 1].size(); i++ )
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:36:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
36 | for ( int i = 0; i < ys[x + 1].size(); i++ )
| ~~^~~~~~~~~~~~~~~~~~
fish.cpp:40:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for ( int i = 1; i < yss.size(); i++ )
| ~~^~~~~~~~~~~~
fish.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for ( int i = 0; i < ys[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
fish.cpp:52:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | while ( lower1 + 1 < ys[x - 1].size() && ys[x - 1][lower1 + 1] <= crtY )
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:54:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while ( upper1 < ys[x - 1].size() && ys[x - 1][upper1] < crtY )
| ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:58:25: warning: unused variable 'prevY' [-Wunused-variable]
58 | int prevY = ys[x - 1][lower1];
| ^~~~~
fish.cpp:62:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | if ( upper1 < ys[x - 1].size() ) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:63:25: warning: unused variable 'prevY' [-Wunused-variable]
63 | int prevY = ys[x - 1][upper1];
| ^~~~~
fish.cpp:69:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
69 | while ( lower2 + 1 < ys[x - 2].size() && ys[x - 2][lower2 + 1] <= crtY )
| ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:71:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
71 | while ( upper2 < ys[x - 2].size() && ys[x - 2][upper2] < crtY )
| ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:75:25: warning: unused variable 'prevY' [-Wunused-variable]
75 | int prevY = ys[x - 2][lower2];
| ^~~~~
fish.cpp:79:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
79 | if ( upper2 < ys[x - 2].size() ) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~
fish.cpp:80:25: warning: unused variable 'prevY' [-Wunused-variable]
80 | int prevY = ys[x - 2][upper2];
| ^~~~~
fish.cpp:91:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
91 | for ( int i = 1; i < ys[x].size(); i++ ) {
| ~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
305 ms |
244796 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '5492851724' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 2 |
Incorrect |
578 ms |
303160 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '4748330365' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
210408 KB |
Output is correct |
| 2 |
Correct |
218 ms |
210004 KB |
Output is correct |
| 3 |
Correct |
305 ms |
222040 KB |
Output is correct |
| 4 |
Correct |
299 ms |
226168 KB |
Output is correct |
| 5 |
Correct |
435 ms |
245336 KB |
Output is correct |
| 6 |
Correct |
430 ms |
245280 KB |
Output is correct |
| 7 |
Correct |
446 ms |
245328 KB |
Output is correct |
| 8 |
Correct |
434 ms |
245420 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 2 |
Correct |
28 ms |
122540 KB |
Output is correct |
| 3 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 4 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 5 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 6 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 7 |
Correct |
27 ms |
122468 KB |
Output is correct |
| 8 |
Correct |
28 ms |
122536 KB |
Output is correct |
| 9 |
Correct |
28 ms |
122736 KB |
Output is correct |
| 10 |
Correct |
31 ms |
123224 KB |
Output is correct |
| 11 |
Incorrect |
29 ms |
122972 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '257536839824' |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 2 |
Correct |
28 ms |
122540 KB |
Output is correct |
| 3 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 4 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 5 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 6 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 7 |
Correct |
27 ms |
122468 KB |
Output is correct |
| 8 |
Correct |
28 ms |
122536 KB |
Output is correct |
| 9 |
Correct |
28 ms |
122736 KB |
Output is correct |
| 10 |
Correct |
31 ms |
123224 KB |
Output is correct |
| 11 |
Incorrect |
29 ms |
122972 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '257536839824' |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 2 |
Correct |
28 ms |
122540 KB |
Output is correct |
| 3 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 4 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 5 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 6 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 7 |
Correct |
27 ms |
122468 KB |
Output is correct |
| 8 |
Correct |
28 ms |
122536 KB |
Output is correct |
| 9 |
Correct |
28 ms |
122736 KB |
Output is correct |
| 10 |
Correct |
31 ms |
123224 KB |
Output is correct |
| 11 |
Incorrect |
29 ms |
122972 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '257536839824' |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
204 ms |
210408 KB |
Output is correct |
| 2 |
Correct |
218 ms |
210004 KB |
Output is correct |
| 3 |
Correct |
305 ms |
222040 KB |
Output is correct |
| 4 |
Correct |
299 ms |
226168 KB |
Output is correct |
| 5 |
Correct |
435 ms |
245336 KB |
Output is correct |
| 6 |
Correct |
430 ms |
245280 KB |
Output is correct |
| 7 |
Correct |
446 ms |
245328 KB |
Output is correct |
| 8 |
Correct |
434 ms |
245420 KB |
Output is correct |
| 9 |
Correct |
714 ms |
320460 KB |
Output is correct |
| 10 |
Correct |
294 ms |
196944 KB |
Output is correct |
| 11 |
Correct |
643 ms |
271444 KB |
Output is correct |
| 12 |
Correct |
30 ms |
122460 KB |
Output is correct |
| 13 |
Correct |
27 ms |
122456 KB |
Output is correct |
| 14 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 15 |
Correct |
28 ms |
122456 KB |
Output is correct |
| 16 |
Correct |
28 ms |
122460 KB |
Output is correct |
| 17 |
Correct |
28 ms |
122500 KB |
Output is correct |
| 18 |
Correct |
206 ms |
210388 KB |
Output is correct |
| 19 |
Correct |
234 ms |
210004 KB |
Output is correct |
| 20 |
Correct |
203 ms |
210000 KB |
Output is correct |
| 21 |
Correct |
210 ms |
210244 KB |
Output is correct |
| 22 |
Incorrect |
677 ms |
320876 KB |
1st lines differ - on the 1st token, expected: '45561826463480', found: '36696784338659' |
| 23 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
305 ms |
244796 KB |
1st lines differ - on the 1st token, expected: '40313272768926', found: '5492851724' |
| 2 |
Halted |
0 ms |
0 KB |
- |
