#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
const ll maxn = 100005;
basic_string<ll> realheights[maxn];
unordered_map<ll, unordered_map<ll,ll>> weights;
basic_string<ll> p[maxn];
basic_string<array<ll,2>> dp[maxn];
basic_string<ll> pref[maxn][2];
basic_string<ll> pref2[maxn][2];
basic_string<ll> suff[maxn][2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
FOR(i,0,M){
Y[i]++;
weights[X[i]][Y[i]] = W[i];
if (X[i] > 0) realheights[X[i]-1].push_back(Y[i]);
if (X[i] > 1) realheights[X[i]-2].push_back(Y[i]);
realheights[X[i]].push_back(Y[i]);
realheights[X[i]+1].push_back(Y[i]);
realheights[X[i]+2].push_back(Y[i]);
}
FOR(i,0,maxn) realheights[i].push_back(0);
FOR(i,0,maxn) realheights[i].push_back(maxn);
FOR(i,0,maxn){
sort(realheights[i].begin(), realheights[i].end());
auto it = unique(realheights[i].begin(), realheights[i].end());
realheights[i].resize(it-realheights[i].begin());
sort(realheights[i].begin(), realheights[i].end());
}
FOR(i,0,maxn){
FOR(k,0,2){
pref[i][k].resize(realheights[i].size());
pref2[i][k].resize(realheights[i].size());
suff[i][k].resize(realheights[i].size());
}
p[i].resize(realheights[i].size());
dp[i].resize(realheights[i].size());
}
FOR(i,0,maxn){
p[i][0] = 0;
ll prev = 0;
FOR(j,1,realheights[i].size()){
p[i][j] = p[i][j-1] + weights[i][realheights[i][j]];
}
}
FOR(i,1,N+1){
FOR(X,0,dp[i].size()){
ll j = realheights[i][X];
FOR(k,0,2){
if (i<2) continue;
ll temp = 0;
ll add = 0;
if (k==0){
if (X==dp[i].size()-1) continue;
ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
temp = max(temp, suff[i-1][0][down] - p[i-1][down]);
temp = max(temp, suff[i-1][1][down] - p[i-1][down]);
// FOR(p,j+1,N+1){
// if (fish[i-1][p]) add += weights[i-1][p];
// temp = max(temp, dp[i-1][p][0] + add);
// temp = max(temp, dp[i-1][p][1] + add);
// }
}
else{
ll down = upper_bound(realheights[i-1].begin(), realheights[i-1].end(), j) - realheights[i-1].begin() - 1;
ll down2 = upper_bound(realheights[i-2].begin(), realheights[i-2].end(), j) - realheights[i-2].begin() - 1;
temp = max(temp, pref[i-1][0][down]);
temp = max(temp, pref[i-1][1][down] + p[i-2][down2]);
// FOR(p,0,j+1) if (fish[i-2][p]) add += weights[i-2][p];
// FOR(p,0,j+1){
// if (fish[i-2][p]) add -= weights[i-2][p];
// temp = max(temp, dp[i-1][p][0]);
// temp = max(temp, dp[i-1][p][1] + add);
// }
}
dp[i][X][k] = temp;
}
}
ll sz = realheights[i].size();
FOR(k,0,2){
ll tempadd = 0;
ll tempadd2 = 0;
FOR(j,0,sz){
tempadd += weights[i][realheights[i][j]];
suff[i][k][j] = dp[i][j][k]+tempadd;
}
FOR(j,0,sz){
tempadd2 -= weights[(i-1)][realheights[i][j]];
pref[i][k][j] = dp[i][j][k] + tempadd2;
pref2[i][k][j] = dp[i][j][k];
}
ll prev = 0;
FOR(j,1,sz){
pref[i][k][j] = max(pref[i][k][j], pref[i][k][j-1]);
pref2[i][k][j] = max(pref2[i][k][j], pref2[i][k][j-1]);
}
FORNEG(j,sz-2,-1){
suff[i][k][j] = max(suff[i][k][j], suff[i][k][j+1]);
}
}
// cout << i << endl;
// cout << suff[2][2][0] << "FUCK" << endl;
}
ll ans = 0;
FOR(i,0,N+1){
FOR(j,0,dp[i].size()){
ans = max(dp[i][j][0], ans);
ans = max(dp[i][j][1], ans);
}
}
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
66 | FOR(j,1,realheights[i].size()){
| ~~~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:66:9: note: in expansion of macro 'FOR'
66 | FOR(j,1,realheights[i].size()){
| ^~~
fish.cpp:65:12: warning: unused variable 'prev' [-Wunused-variable]
65 | ll prev = 0;
| ^~~~
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
75 | FOR(X,0,dp[i].size()){
| ~~~~~~~~~~~~~~~~
fish.cpp:75:9: note: in expansion of macro 'FOR'
75 | FOR(X,0,dp[i].size()){
| ^~~
fish.cpp:84:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | if (X==dp[i].size()-1) continue;
| ~^~~~~~~~~~~~~~~~
fish.cpp:82:20: warning: unused variable 'add' [-Wunused-variable]
82 | ll add = 0;
| ^~~
fish.cpp:133:16: warning: unused variable 'prev' [-Wunused-variable]
133 | ll prev = 0;
| ^~~~
fish.cpp:7:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::__cxx11::basic_string<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
7 | #define FOR(i,x,y) for(ll i=x; i<y; i++)
......
160 | FOR(j,0,dp[i].size()){
| ~~~~~~~~~~~~~~~~
fish.cpp:160:9: note: in expansion of macro 'FOR'
160 | FOR(j,0,dp[i].size()){
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
117672 KB |
Output is correct |
2 |
Correct |
221 ms |
127396 KB |
Output is correct |
3 |
Correct |
100 ms |
86328 KB |
Output is correct |
4 |
Correct |
98 ms |
86188 KB |
Output is correct |
5 |
Correct |
822 ms |
300464 KB |
Output is correct |
6 |
Execution timed out |
1038 ms |
296136 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
83140 KB |
Output is correct |
2 |
Correct |
309 ms |
137100 KB |
Output is correct |
3 |
Correct |
329 ms |
146112 KB |
Output is correct |
4 |
Correct |
176 ms |
117816 KB |
Output is correct |
5 |
Correct |
238 ms |
127392 KB |
Output is correct |
6 |
Correct |
97 ms |
83128 KB |
Output is correct |
7 |
Correct |
98 ms |
83140 KB |
Output is correct |
8 |
Correct |
91 ms |
83140 KB |
Output is correct |
9 |
Correct |
84 ms |
83200 KB |
Output is correct |
10 |
Correct |
108 ms |
86148 KB |
Output is correct |
11 |
Correct |
91 ms |
86216 KB |
Output is correct |
12 |
Correct |
206 ms |
127512 KB |
Output is correct |
13 |
Correct |
252 ms |
139548 KB |
Output is correct |
14 |
Correct |
208 ms |
122804 KB |
Output is correct |
15 |
Correct |
211 ms |
114732 KB |
Output is correct |
16 |
Correct |
213 ms |
122644 KB |
Output is correct |
17 |
Correct |
227 ms |
129172 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
86212 KB |
Output is correct |
2 |
Correct |
92 ms |
86292 KB |
Output is correct |
3 |
Correct |
184 ms |
100552 KB |
Output is correct |
4 |
Correct |
160 ms |
97480 KB |
Output is correct |
5 |
Correct |
264 ms |
110996 KB |
Output is correct |
6 |
Correct |
260 ms |
110276 KB |
Output is correct |
7 |
Correct |
260 ms |
111200 KB |
Output is correct |
8 |
Correct |
260 ms |
110792 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
83140 KB |
Output is correct |
2 |
Correct |
79 ms |
83304 KB |
Output is correct |
3 |
Correct |
75 ms |
83140 KB |
Output is correct |
4 |
Correct |
77 ms |
83144 KB |
Output is correct |
5 |
Correct |
76 ms |
83172 KB |
Output is correct |
6 |
Correct |
82 ms |
83140 KB |
Output is correct |
7 |
Correct |
88 ms |
83184 KB |
Output is correct |
8 |
Correct |
78 ms |
83192 KB |
Output is correct |
9 |
Correct |
83 ms |
83144 KB |
Output is correct |
10 |
Correct |
81 ms |
83524 KB |
Output is correct |
11 |
Correct |
82 ms |
83356 KB |
Output is correct |
12 |
Correct |
92 ms |
83368 KB |
Output is correct |
13 |
Correct |
87 ms |
83024 KB |
Output is correct |
14 |
Correct |
97 ms |
83396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
83140 KB |
Output is correct |
2 |
Correct |
79 ms |
83304 KB |
Output is correct |
3 |
Correct |
75 ms |
83140 KB |
Output is correct |
4 |
Correct |
77 ms |
83144 KB |
Output is correct |
5 |
Correct |
76 ms |
83172 KB |
Output is correct |
6 |
Correct |
82 ms |
83140 KB |
Output is correct |
7 |
Correct |
88 ms |
83184 KB |
Output is correct |
8 |
Correct |
78 ms |
83192 KB |
Output is correct |
9 |
Correct |
83 ms |
83144 KB |
Output is correct |
10 |
Correct |
81 ms |
83524 KB |
Output is correct |
11 |
Correct |
82 ms |
83356 KB |
Output is correct |
12 |
Correct |
92 ms |
83368 KB |
Output is correct |
13 |
Correct |
87 ms |
83024 KB |
Output is correct |
14 |
Correct |
97 ms |
83396 KB |
Output is correct |
15 |
Correct |
78 ms |
83400 KB |
Output is correct |
16 |
Correct |
94 ms |
83740 KB |
Output is correct |
17 |
Correct |
139 ms |
95428 KB |
Output is correct |
18 |
Correct |
129 ms |
93380 KB |
Output is correct |
19 |
Correct |
153 ms |
94668 KB |
Output is correct |
20 |
Correct |
130 ms |
92872 KB |
Output is correct |
21 |
Correct |
127 ms |
92480 KB |
Output is correct |
22 |
Correct |
164 ms |
102080 KB |
Output is correct |
23 |
Correct |
137 ms |
88560 KB |
Output is correct |
24 |
Correct |
130 ms |
95176 KB |
Output is correct |
25 |
Correct |
73 ms |
83544 KB |
Output is correct |
26 |
Correct |
115 ms |
87236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
79 ms |
83140 KB |
Output is correct |
2 |
Correct |
79 ms |
83304 KB |
Output is correct |
3 |
Correct |
75 ms |
83140 KB |
Output is correct |
4 |
Correct |
77 ms |
83144 KB |
Output is correct |
5 |
Correct |
76 ms |
83172 KB |
Output is correct |
6 |
Correct |
82 ms |
83140 KB |
Output is correct |
7 |
Correct |
88 ms |
83184 KB |
Output is correct |
8 |
Correct |
78 ms |
83192 KB |
Output is correct |
9 |
Correct |
83 ms |
83144 KB |
Output is correct |
10 |
Correct |
81 ms |
83524 KB |
Output is correct |
11 |
Correct |
82 ms |
83356 KB |
Output is correct |
12 |
Correct |
92 ms |
83368 KB |
Output is correct |
13 |
Correct |
87 ms |
83024 KB |
Output is correct |
14 |
Correct |
97 ms |
83396 KB |
Output is correct |
15 |
Correct |
78 ms |
83400 KB |
Output is correct |
16 |
Correct |
94 ms |
83740 KB |
Output is correct |
17 |
Correct |
139 ms |
95428 KB |
Output is correct |
18 |
Correct |
129 ms |
93380 KB |
Output is correct |
19 |
Correct |
153 ms |
94668 KB |
Output is correct |
20 |
Correct |
130 ms |
92872 KB |
Output is correct |
21 |
Correct |
127 ms |
92480 KB |
Output is correct |
22 |
Correct |
164 ms |
102080 KB |
Output is correct |
23 |
Correct |
137 ms |
88560 KB |
Output is correct |
24 |
Correct |
130 ms |
95176 KB |
Output is correct |
25 |
Correct |
73 ms |
83544 KB |
Output is correct |
26 |
Correct |
115 ms |
87236 KB |
Output is correct |
27 |
Correct |
107 ms |
85220 KB |
Output is correct |
28 |
Correct |
317 ms |
133940 KB |
Output is correct |
29 |
Correct |
557 ms |
187384 KB |
Output is correct |
30 |
Correct |
858 ms |
272996 KB |
Output is correct |
31 |
Correct |
824 ms |
265084 KB |
Output is correct |
32 |
Correct |
413 ms |
145980 KB |
Output is correct |
33 |
Correct |
898 ms |
285892 KB |
Output is correct |
34 |
Correct |
918 ms |
286200 KB |
Output is correct |
35 |
Correct |
274 ms |
131276 KB |
Output is correct |
36 |
Correct |
710 ms |
228804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
86212 KB |
Output is correct |
2 |
Correct |
92 ms |
86292 KB |
Output is correct |
3 |
Correct |
184 ms |
100552 KB |
Output is correct |
4 |
Correct |
160 ms |
97480 KB |
Output is correct |
5 |
Correct |
264 ms |
110996 KB |
Output is correct |
6 |
Correct |
260 ms |
110276 KB |
Output is correct |
7 |
Correct |
260 ms |
111200 KB |
Output is correct |
8 |
Correct |
260 ms |
110792 KB |
Output is correct |
9 |
Correct |
414 ms |
154820 KB |
Output is correct |
10 |
Correct |
195 ms |
105160 KB |
Output is correct |
11 |
Correct |
393 ms |
127096 KB |
Output is correct |
12 |
Correct |
70 ms |
83140 KB |
Output is correct |
13 |
Correct |
72 ms |
83144 KB |
Output is correct |
14 |
Correct |
112 ms |
83140 KB |
Output is correct |
15 |
Correct |
74 ms |
83148 KB |
Output is correct |
16 |
Correct |
70 ms |
83140 KB |
Output is correct |
17 |
Correct |
73 ms |
83140 KB |
Output is correct |
18 |
Correct |
126 ms |
86288 KB |
Output is correct |
19 |
Correct |
117 ms |
86384 KB |
Output is correct |
20 |
Correct |
92 ms |
86216 KB |
Output is correct |
21 |
Correct |
98 ms |
86324 KB |
Output is correct |
22 |
Correct |
512 ms |
153164 KB |
Output is correct |
23 |
Correct |
507 ms |
162248 KB |
Output is correct |
24 |
Correct |
611 ms |
174216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
117672 KB |
Output is correct |
2 |
Correct |
221 ms |
127396 KB |
Output is correct |
3 |
Correct |
100 ms |
86328 KB |
Output is correct |
4 |
Correct |
98 ms |
86188 KB |
Output is correct |
5 |
Correct |
822 ms |
300464 KB |
Output is correct |
6 |
Execution timed out |
1038 ms |
296136 KB |
Time limit exceeded |
7 |
Halted |
0 ms |
0 KB |
- |