#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
ll dp[300001],sl[300001],sr[300001],si[300001],mmax[100001],mmax_mi[100001],ans,ma;
map<pii,int> val;
vector<pii> vv,v,temp_val; //(index, height)
queue<pii> temp_col; //(height, index)
queue<pii> col[100001]; //(height, value)
set<int> cor_x;
queue<int> qx;
multiset<ll, greater<ll>> mo,le;
ll max_weights(int n, int m, vector<int> X, vector<int> Y, vector<int> W) {
for (int i=0; i<m; ++i) {
val[pii(X[i],Y[i])]=W[i];
vv.push_back(pii(X[i],Y[i]));
cor_x.insert(X[i]);
if (X[i]) v.push_back(pii(X[i]-1,Y[i]));
if (X[i]<n-1) v.push_back(pii(X[i]+1,Y[i]));
}
for (auto s : cor_x) qx.push(s);
sort(vv.begin(),vv.end());
for (auto s : vv) col[s.first].push(pii(s.second,val[pii(s.first,s.second)]));
sort(v.begin(),v.end());
int i=1,pre=-1;
for (auto s : v) {
int x=s.first, y=s.second;
if (x==pre) { //same x_cor
si[i]=si[i-1];
while (!col[x].empty() & y>=col[x].front().first) {
si[i]+=col[x].front().second;
col[x].pop();
}
sr[i]=sr[i-1]+val[pii(x+1,y)];
sl[i]=sl[i-1]+val[pii(x-1,y)];
} else { //new x_cor
while (!col[x].empty() & y>=col[x].front().first) {
si[i]+=col[x].front().second;
col[x].pop();
}
sr[i]=val[pii(x+1,y)];
sl[i]=val[pii(x-1,y)];
//clear more, less, temp
mo.clear();
le.clear();
while (!temp_col.empty()) temp_col.pop();
for (auto h : temp_val) {
mo.insert(dp[h.first]);
temp_col.push(pii(h.second,h.first));
}
temp_val.clear();
//find max from all previous col (ma)
while (qx.front()<x-2) {
ma=max(ma,mmax[qx.front()]);
qx.pop();
}
if (qx.front()==x-2) ma=max(ma,mmax_mi[qx.front()]);
}
//more to less
while (!temp_col.empty() && temp_col.front().first<y) {
int idx=temp_col.front().second;
temp_col.pop();
auto it=mo.find(dp[idx]);
mo.erase(it);
le.insert(dp[idx]-si[idx]-sr[idx]);
}
dp[i]=ma+sl[i]+sr[i];
if (!mo.empty()) dp[i]=max(dp[i],*(mo.begin())-si[i]+sr[i]);
if (!le.empty()) dp[i]=max(dp[i],*(le.begin())+sl[i]+sr[i]);
mmax_mi[x]=max(mmax_mi[x],dp[i]-sr[i]);
mmax[x]=max(mmax[x],dp[i]);
ans=max(ans,dp[i]);
temp_val.push_back(pii(i,y));
++i;
if (x!=pre) pre=x;
}
return ans;
}
Compilation message
fish.cpp: In function 'll max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:40:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
40 | while (!col[x].empty() & y>=col[x].front().first) {
| ~^~~~~~~~~~~~~~~~~~~~~~
fish.cpp:48:39: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
48 | while (!col[x].empty() & y>=col[x].front().first) {
| ~^~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
149 ms |
86036 KB |
Output is correct |
2 |
Correct |
180 ms |
90344 KB |
Output is correct |
3 |
Correct |
41 ms |
67556 KB |
Output is correct |
4 |
Correct |
45 ms |
67636 KB |
Output is correct |
5 |
Runtime error |
722 ms |
276668 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
67608 KB |
Output is correct |
2 |
Incorrect |
419 ms |
114700 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '80957127419834' |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
67532 KB |
Output is correct |
2 |
Correct |
40 ms |
67584 KB |
Output is correct |
3 |
Incorrect |
147 ms |
81748 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '41123459278886' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
67560 KB |
Output is correct |
2 |
Correct |
40 ms |
67668 KB |
Output is correct |
3 |
Correct |
43 ms |
67592 KB |
Output is correct |
4 |
Correct |
42 ms |
67584 KB |
Output is correct |
5 |
Correct |
37 ms |
67604 KB |
Output is correct |
6 |
Correct |
41 ms |
67668 KB |
Output is correct |
7 |
Correct |
41 ms |
67620 KB |
Output is correct |
8 |
Correct |
44 ms |
67644 KB |
Output is correct |
9 |
Incorrect |
41 ms |
67748 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
67560 KB |
Output is correct |
2 |
Correct |
40 ms |
67668 KB |
Output is correct |
3 |
Correct |
43 ms |
67592 KB |
Output is correct |
4 |
Correct |
42 ms |
67584 KB |
Output is correct |
5 |
Correct |
37 ms |
67604 KB |
Output is correct |
6 |
Correct |
41 ms |
67668 KB |
Output is correct |
7 |
Correct |
41 ms |
67620 KB |
Output is correct |
8 |
Correct |
44 ms |
67644 KB |
Output is correct |
9 |
Incorrect |
41 ms |
67748 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
67560 KB |
Output is correct |
2 |
Correct |
40 ms |
67668 KB |
Output is correct |
3 |
Correct |
43 ms |
67592 KB |
Output is correct |
4 |
Correct |
42 ms |
67584 KB |
Output is correct |
5 |
Correct |
37 ms |
67604 KB |
Output is correct |
6 |
Correct |
41 ms |
67668 KB |
Output is correct |
7 |
Correct |
41 ms |
67620 KB |
Output is correct |
8 |
Correct |
44 ms |
67644 KB |
Output is correct |
9 |
Incorrect |
41 ms |
67748 KB |
1st lines differ - on the 1st token, expected: '216624184325', found: '582529633250' |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
67532 KB |
Output is correct |
2 |
Correct |
40 ms |
67584 KB |
Output is correct |
3 |
Incorrect |
147 ms |
81748 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '41123459278886' |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
149 ms |
86036 KB |
Output is correct |
2 |
Correct |
180 ms |
90344 KB |
Output is correct |
3 |
Correct |
41 ms |
67556 KB |
Output is correct |
4 |
Correct |
45 ms |
67636 KB |
Output is correct |
5 |
Runtime error |
722 ms |
276668 KB |
Execution killed with signal 11 |
6 |
Halted |
0 ms |
0 KB |
- |