#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
template<typename S, typename T>
void xmax(S&a, T const&b){
if(b>a) a = b;
}
struct Fish{
int y;
ll w;
ll left = 0, middle = 0, right = 0;
};
struct DP{
vector<ll> up, down;
ll zero_with = 0, zero_without = 0;
ll next_zero_with = 0, next_zero_without = 0;
};
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
vector<vector<Fish> > ev(N+2);
for(int i=0; i<M; ++i){
ev[X[i]+1].push_back(Fish{Y[i], W[i]});
}
for(auto &e : ev) {
e.push_back(Fish{-1, 0});
e.push_back(Fish{N+1, 0});
sort(e.begin(), e.end(), [&](auto const&a, auto const&b){ return a.y < b.y; });
for(int i=1; i<(int)e.size(); ++i){
e[i].middle = e[i-1].middle + e[i].w;
}
}
for(int x=0; x<=N; ++x){
auto &L = ev[x], &R = ev[x+1];
int i = (int)L.size()-1, j = (int)R.size()-1;
while(i >= 0 && j >= 0){
auto &l = L[i], &r = R[j];
if(l.y < r.y){
r.left = l.middle;
--j;
} else if(l.y > r.y){
l.right = r.middle;
--i;
} else {
l.right = r.middle;
r.left = l.middle;
--i; --j;
}
}
}
DP prev;
prev.up.assign(2, 0);
prev.down.assign(2, 0);
for(int x=1; x<=N+1; ++x){
auto &you = ev[x-1];
auto &me = ev[x];
/*cerr << "at: " << x << "\n";
for(auto &e : me){
cerr << e.y << " " << e.w << " : " << e.left << " / " << e.middle << " / " << e.right << "\n";
}*/
/* compute up: For each height
* - find best pred
* - add left
* - subtract me (due to next up)
* - check transform into down
*
* compute down: For each height
* - find best pred (or cur.up)
* - add right
* - subtract me (due to prev down)
* - check transform to zero.
*
*/
DP cur;
cur.up.assign(me.size(), 0);
cur.down.assign(me.size(), 0);
/// compute up
{
int i = (int)you.size()-1, j = (int)me.size()-1;
while(i >= 0 && j >= 0){
if(you[i].y > me[j].y) --i;
else {
cur.up[j] = prev.up[i];
--j;
}
}
}
// add left - middle
// also consider the zero start
for(int i=0; i<(int)me.size(); ++i){
xmax(cur.up[i], prev.zero_without);
cur.up[i] += me[i].left;
xmax(cur.up[i], prev.zero_with);
cur.up[i] -= me[i].middle;
}
/// update zeros
cur.zero_with = prev.next_zero_with;
cur.zero_without = prev.next_zero_without;
/// compute down
{
// find best pred
int i = 0, j = 0;
while(i < (int)you.size() && j < (int)me.size()){
if(you[i].y < me[j].y) ++i;
else {
cur.down[j] = max(prev.down[i], cur.up[j] + 2*me[j].middle);
++j;
}
}
}
// add right - middle
// consider creating zeros
for(int i = (int)me.size()-1; i > 0; --i){
cur.down[i] -= me[i].middle;
xmax(cur.next_zero_without, cur.down[i]);
cur.down[i] += me[i].right;
xmax(cur.next_zero_with, cur.down[i]);
}
/// turn values into prefix / suffic maxima
// move up
for(int i=1; i<(int)me.size(); ++i){
xmax(cur.up[i], cur.up[i-1]);
}
// move down
for(int i = (int)me.size()-1; i > 0; --i){
xmax(cur.down[i-1], cur.down[i]);
}
prev = move(cur);
}
return max(prev.zero_with, prev.up[0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
17100 KB |
Output is correct |
| 2 |
Correct |
63 ms |
19760 KB |
Output is correct |
| 3 |
Correct |
22 ms |
12008 KB |
Output is correct |
| 4 |
Correct |
21 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
144 ms |
32224 KB |
Output is correct |
| 6 |
Correct |
177 ms |
37232 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
22 ms |
12000 KB |
Output is correct |
| 3 |
Correct |
46 ms |
16588 KB |
Output is correct |
| 4 |
Correct |
39 ms |
15924 KB |
Output is correct |
| 5 |
Correct |
77 ms |
23324 KB |
Output is correct |
| 6 |
Correct |
64 ms |
23244 KB |
Output is correct |
| 7 |
Correct |
76 ms |
23316 KB |
Output is correct |
| 8 |
Correct |
66 ms |
23256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '3', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
11988 KB |
Output is correct |
| 2 |
Correct |
22 ms |
12000 KB |
Output is correct |
| 3 |
Correct |
46 ms |
16588 KB |
Output is correct |
| 4 |
Correct |
39 ms |
15924 KB |
Output is correct |
| 5 |
Correct |
77 ms |
23324 KB |
Output is correct |
| 6 |
Correct |
64 ms |
23244 KB |
Output is correct |
| 7 |
Correct |
76 ms |
23316 KB |
Output is correct |
| 8 |
Correct |
66 ms |
23256 KB |
Output is correct |
| 9 |
Incorrect |
71 ms |
23312 KB |
1st lines differ - on the 1st token, expected: '99999', found: '66666' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
17100 KB |
Output is correct |
| 2 |
Correct |
63 ms |
19760 KB |
Output is correct |
| 3 |
Correct |
22 ms |
12008 KB |
Output is correct |
| 4 |
Correct |
21 ms |
11988 KB |
Output is correct |
| 5 |
Correct |
144 ms |
32224 KB |
Output is correct |
| 6 |
Correct |
177 ms |
37232 KB |
Output is correct |
| 7 |
Incorrect |
0 ms |
212 KB |
1st lines differ - on the 1st token, expected: '2', found: '1' |
| 8 |
Halted |
0 ms |
0 KB |
- |
