#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pier {
int x, y;
ll fishL = 0, fishAct = 0, fishR = 0, val[2] = {0, 0};
};
struct Fish {
bool req;
int y;
ll pds;
};
const ll N = 1e5 + 42, INF = 1e15 + 42;
ll sz[N];
vector<Fish> fish[N];
vector<Pier> pier[N];
unordered_map<ll, ll> nb[N];
ll max_weights(int n, int M, vector<int> X, vector<int> Y, vector<int> W) {
for(int i = 0; i < M; i++) {
Y[i] += 1;
fish[X[i]].push_back({false, Y[i], W[i]});
for(int j = max(X[i]-2, 0); j < min(X[i]+3, n); j++)
fish[j].push_back({true, Y[i], 0});
pier[X[i]].push_back({X[i], Y[i]});
if(X[i] != 0)
pier[X[i]-1].push_back({X[i], Y[i]});
if(X[i] != n-1)
pier[X[i]+1].push_back({X[i], Y[i]});
}
for(int i = 0; i < n; i++) {
sort(fish[i].begin(), fish[i].end(),
[](Fish a, Fish b) {
if(a.y == b.y) {
if(a.req == b.req)
return false;
return b.req;
}
return a.y < b.y;
});
ll sum = 0;
for(Fish f : fish[i]) {
if(f.req) {
nb[i][f.y] = sum;
} else {
sum += f.pds;
}
}
}
for(int i = 0; i < n; i++) {
for(Pier& p : pier[i]) {
if(i != 0)
p.fishL = nb[i-1][p.y];
p.fishAct = nb[i][p.y];
if(i != n-1)
p.fishR = nb[i+1][p.y];
}
}
for(int i = 0; i < n; i++)
sort(pier[i].begin(), pier[i].end(),
[](Pier a, Pier b) {
return a.y < b.y;
});
for(int i = 0; i < n; i++)
sz[i] = (ll)pier[i].size();
ll maxi = 0;
for(int i = 0; i < n; i++) {
for(Pier& p : pier[i]) {
p.val[0] = maxi + p.fishL - p.fishAct;
p.val[1] = maxi + p.fishL + p.fishR;
}
ll id[2] = {0, 0}, maxiLL = -INF, maxiL = -INF;
for(Pier& p : pier[i]) {
if(i > 0) {
while(id[0] < sz[i-1] && pier[i-1][id[0]].y <= p.y) {
maxiL = max(maxiL, pier[i-1][id[0]].val[0]);
id[0]++;
}
}
if(i > 1) {
while(id[1] < sz[i-2] && pier[i-2][id[1]].y <= p.y) {
maxiLL = max(maxiLL, pier[i-2][id[1]].val[1] - pier[i-2][id[1]].fishR - pier[i-2][id[1]].fishAct);
id[1]++;
}
}
p.val[0] = max(p.val[0], max(maxiL, maxiLL) - p.fishAct + p.fishL);
p.val[1] = max(p.val[1], max(maxiL, maxiLL) + p.fishL + p.fishR);
}
if(i == 0) {
id[0] = id[1] = -1;
} else if(i == 1) {
id[0] = sz[i-1]-1;
id[1] = -1;
} else {
id[0] = sz[i-1]-1;
id[1] = sz[i-2]-1;
}
maxiLL = maxiL = -INF;
reverse(pier[i].begin(), pier[i].end());
for(Pier& p : pier[i]) {
if(i > 0) {
while(id[0] >= 0 && pier[i-1][id[0]].y >= p.y) {
maxiL = max(maxiL, pier[i-1][id[0]].val[1]);
id[0]--;
}
}
if(i > 1) {
while(id[1] >= 0 && pier[i-2][id[1]].y >= p.y) {
maxiLL = max(maxiLL, pier[i-2][id[1]].val[1]);
id[1]--;
}
}
p.val[0] = max(p.val[0], maxiLL - p.fishAct);
p.val[1] = max(p.val[1], max(maxiLL, maxiL - p.fishAct) + p.fishR);
}
reverse(pier[i].begin(), pier[i].end());
if(i > 1) {
for(Pier p : pier[i-2])
maxi = max(maxi, max(p.val[0], p.val[1]));
}
}
for(Pier p : pier[n-1])
maxi = max(maxi, max(p.val[0], p.val[1]));
for(Pier p : pier[n-2])
maxi = max(maxi, max(p.val[0], p.val[1]));
return maxi;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
36376 KB |
Output is correct |
2 |
Correct |
147 ms |
43856 KB |
Output is correct |
3 |
Correct |
7 ms |
11220 KB |
Output is correct |
4 |
Correct |
7 ms |
11220 KB |
Output is correct |
5 |
Correct |
595 ms |
161636 KB |
Output is correct |
6 |
Correct |
748 ms |
189344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
10452 KB |
Output is correct |
2 |
Correct |
285 ms |
64072 KB |
Output is correct |
3 |
Correct |
324 ms |
75464 KB |
Output is correct |
4 |
Correct |
118 ms |
37208 KB |
Output is correct |
5 |
Correct |
149 ms |
44808 KB |
Output is correct |
6 |
Correct |
6 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
6 ms |
10452 KB |
Output is correct |
9 |
Correct |
7 ms |
10452 KB |
Output is correct |
10 |
Correct |
7 ms |
11220 KB |
Output is correct |
11 |
Correct |
7 ms |
11220 KB |
Output is correct |
12 |
Correct |
171 ms |
45600 KB |
Output is correct |
13 |
Correct |
201 ms |
55672 KB |
Output is correct |
14 |
Correct |
134 ms |
41020 KB |
Output is correct |
15 |
Correct |
141 ms |
40632 KB |
Output is correct |
16 |
Correct |
138 ms |
41036 KB |
Output is correct |
17 |
Correct |
156 ms |
46472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11220 KB |
Output is correct |
2 |
Correct |
7 ms |
11220 KB |
Output is correct |
3 |
Correct |
135 ms |
39652 KB |
Output is correct |
4 |
Correct |
101 ms |
31800 KB |
Output is correct |
5 |
Correct |
279 ms |
62796 KB |
Output is correct |
6 |
Correct |
251 ms |
63016 KB |
Output is correct |
7 |
Correct |
247 ms |
62952 KB |
Output is correct |
8 |
Correct |
246 ms |
63016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10452 KB |
Output is correct |
2 |
Correct |
6 ms |
10452 KB |
Output is correct |
3 |
Correct |
6 ms |
10488 KB |
Output is correct |
4 |
Correct |
6 ms |
10496 KB |
Output is correct |
5 |
Correct |
6 ms |
10488 KB |
Output is correct |
6 |
Correct |
5 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
6 ms |
10452 KB |
Output is correct |
9 |
Correct |
6 ms |
10708 KB |
Output is correct |
10 |
Correct |
9 ms |
11412 KB |
Output is correct |
11 |
Incorrect |
7 ms |
10836 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '278080972720' |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10452 KB |
Output is correct |
2 |
Correct |
6 ms |
10452 KB |
Output is correct |
3 |
Correct |
6 ms |
10488 KB |
Output is correct |
4 |
Correct |
6 ms |
10496 KB |
Output is correct |
5 |
Correct |
6 ms |
10488 KB |
Output is correct |
6 |
Correct |
5 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
6 ms |
10452 KB |
Output is correct |
9 |
Correct |
6 ms |
10708 KB |
Output is correct |
10 |
Correct |
9 ms |
11412 KB |
Output is correct |
11 |
Incorrect |
7 ms |
10836 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '278080972720' |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
10452 KB |
Output is correct |
2 |
Correct |
6 ms |
10452 KB |
Output is correct |
3 |
Correct |
6 ms |
10488 KB |
Output is correct |
4 |
Correct |
6 ms |
10496 KB |
Output is correct |
5 |
Correct |
6 ms |
10488 KB |
Output is correct |
6 |
Correct |
5 ms |
10452 KB |
Output is correct |
7 |
Correct |
5 ms |
10452 KB |
Output is correct |
8 |
Correct |
6 ms |
10452 KB |
Output is correct |
9 |
Correct |
6 ms |
10708 KB |
Output is correct |
10 |
Correct |
9 ms |
11412 KB |
Output is correct |
11 |
Incorrect |
7 ms |
10836 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '278080972720' |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
11220 KB |
Output is correct |
2 |
Correct |
7 ms |
11220 KB |
Output is correct |
3 |
Correct |
135 ms |
39652 KB |
Output is correct |
4 |
Correct |
101 ms |
31800 KB |
Output is correct |
5 |
Correct |
279 ms |
62796 KB |
Output is correct |
6 |
Correct |
251 ms |
63016 KB |
Output is correct |
7 |
Correct |
247 ms |
62952 KB |
Output is correct |
8 |
Correct |
246 ms |
63016 KB |
Output is correct |
9 |
Correct |
297 ms |
75524 KB |
Output is correct |
10 |
Correct |
207 ms |
55200 KB |
Output is correct |
11 |
Correct |
414 ms |
99872 KB |
Output is correct |
12 |
Correct |
5 ms |
10488 KB |
Output is correct |
13 |
Correct |
6 ms |
10452 KB |
Output is correct |
14 |
Correct |
7 ms |
10452 KB |
Output is correct |
15 |
Correct |
7 ms |
10452 KB |
Output is correct |
16 |
Correct |
6 ms |
10452 KB |
Output is correct |
17 |
Correct |
6 ms |
10452 KB |
Output is correct |
18 |
Correct |
9 ms |
11244 KB |
Output is correct |
19 |
Correct |
9 ms |
11220 KB |
Output is correct |
20 |
Correct |
8 ms |
11220 KB |
Output is correct |
21 |
Correct |
7 ms |
11220 KB |
Output is correct |
22 |
Incorrect |
302 ms |
73480 KB |
1st lines differ - on the 1st token, expected: '45561826463480', found: '45542247608505' |
23 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
122 ms |
36376 KB |
Output is correct |
2 |
Correct |
147 ms |
43856 KB |
Output is correct |
3 |
Correct |
7 ms |
11220 KB |
Output is correct |
4 |
Correct |
7 ms |
11220 KB |
Output is correct |
5 |
Correct |
595 ms |
161636 KB |
Output is correct |
6 |
Correct |
748 ms |
189344 KB |
Output is correct |
7 |
Correct |
7 ms |
10452 KB |
Output is correct |
8 |
Correct |
285 ms |
64072 KB |
Output is correct |
9 |
Correct |
324 ms |
75464 KB |
Output is correct |
10 |
Correct |
118 ms |
37208 KB |
Output is correct |
11 |
Correct |
149 ms |
44808 KB |
Output is correct |
12 |
Correct |
6 ms |
10452 KB |
Output is correct |
13 |
Correct |
5 ms |
10452 KB |
Output is correct |
14 |
Correct |
6 ms |
10452 KB |
Output is correct |
15 |
Correct |
7 ms |
10452 KB |
Output is correct |
16 |
Correct |
7 ms |
11220 KB |
Output is correct |
17 |
Correct |
7 ms |
11220 KB |
Output is correct |
18 |
Correct |
171 ms |
45600 KB |
Output is correct |
19 |
Correct |
201 ms |
55672 KB |
Output is correct |
20 |
Correct |
134 ms |
41020 KB |
Output is correct |
21 |
Correct |
141 ms |
40632 KB |
Output is correct |
22 |
Correct |
138 ms |
41036 KB |
Output is correct |
23 |
Correct |
156 ms |
46472 KB |
Output is correct |
24 |
Correct |
7 ms |
11220 KB |
Output is correct |
25 |
Correct |
7 ms |
11220 KB |
Output is correct |
26 |
Correct |
135 ms |
39652 KB |
Output is correct |
27 |
Correct |
101 ms |
31800 KB |
Output is correct |
28 |
Correct |
279 ms |
62796 KB |
Output is correct |
29 |
Correct |
251 ms |
63016 KB |
Output is correct |
30 |
Correct |
247 ms |
62952 KB |
Output is correct |
31 |
Correct |
246 ms |
63016 KB |
Output is correct |
32 |
Correct |
6 ms |
10452 KB |
Output is correct |
33 |
Correct |
6 ms |
10452 KB |
Output is correct |
34 |
Correct |
6 ms |
10488 KB |
Output is correct |
35 |
Correct |
6 ms |
10496 KB |
Output is correct |
36 |
Correct |
6 ms |
10488 KB |
Output is correct |
37 |
Correct |
5 ms |
10452 KB |
Output is correct |
38 |
Correct |
5 ms |
10452 KB |
Output is correct |
39 |
Correct |
6 ms |
10452 KB |
Output is correct |
40 |
Correct |
6 ms |
10708 KB |
Output is correct |
41 |
Correct |
9 ms |
11412 KB |
Output is correct |
42 |
Incorrect |
7 ms |
10836 KB |
1st lines differ - on the 1st token, expected: '278622587073', found: '278080972720' |
43 |
Halted |
0 ms |
0 KB |
- |