#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using lint=long long;
const int lim=1e5+100;
using pii=pair<int,lint>;
int n,m;
vector<int>inds[lim];
vector<lint> dp[lim],up[lim];
vector<pii>pref[lim];
lint p(int i,int l,int r){
if(n<=i)return 0;
auto rp=lower_bound(pref[i].begin(),pref[i].end(),pii{r+1,0}),
lp=lower_bound(pref[i].begin(),pref[i].end(),pii{l,0});
rp--;
if(lp==pref[i].begin())return rp->second;
lp--;
return rp->second-lp->second;
}
lint max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W) {
n=N,m=M;
for(int i=0;i<m;i++){
pref[X[i]].push_back({Y[i]+1,W[i]});
}
for(int i=0;i<n;i++){
pref[i].push_back({0,0});
pref[i].push_back({n+6,0});
sort(pref[i].begin(),pref[i].end());
for(int j=0;j<size(pref[i]);j++){
if(pref[i][j].first)inds[i].push_back(pref[i][j].first-1);
}
for(int j=1;j<size(pref[i]);j++){
pref[i][j].second+=pref[i][j-1].second;
}
}
dp[0].resize(inds[0].size());
up[0].resize(inds[0].size());
for(int i=0;i<size(dp[0]);i++){
dp[0][i]=pref[0][i+1].second;
up[0][i]=0;
}
for(int i=1;i<n;i++){
dp[i].resize(inds[i].size());
up[i].resize(inds[i].size());
lint max1=0;
int pp=0;
for(int j=0;j<size(dp[i]);j++){
while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
max1=max(max1,up[i-1][pp]-p(i-1,0,inds[i-1][pp]));
pp++;
}
dp[i][j]=max(dp[i][j],max1+p(i-1,0,inds[i][j])+p(i+1,0,inds[i][j]));
up[i][j]=max(up[i][j],max1+p(i-1,0,inds[i][j]));
auto p=upper_bound(inds[i-1].begin(),inds[i-1].end(),inds[i][j]);
if(p!=inds[i-1].begin()){
p--;
up[i][j]=max(up[i][j],dp[i-1][p-inds[i-1].begin()]);
}
}
max1=0;
pp=size(up[i-1]);
pp--;
for(int j=int(size(dp[i]))-1;0<=j;j--){
while(0<=pp&&inds[i][j]<=inds[i-1][pp]){
max1=max(max1,dp[i-1][pp]);
pp--;
}
dp[i][j]=max(dp[i][j],max1-p(i,0,inds[i][j])+p(i+1,0,inds[i][j]));
}
}
lint ans=0;
for(int i=0;i<size(dp[n-1]);i++){
ans=max(ans,dp[n-1][i]);
}
return ans;
}
Compilation message
fish.cpp: In function 'lint max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:35:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int j=0;j<size(pref[i]);j++){
| ~^~~~~~~~~~~~~~
fish.cpp:38:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int j=1;j<size(pref[i]);j++){
| ~^~~~~~~~~~~~~~
fish.cpp:44:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
44 | for(int i=0;i<size(dp[0]);i++){
| ~^~~~~~~~~~~~
fish.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int j=0;j<size(dp[i]);j++){
| ~^~~~~~~~~~~~
fish.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
| ~~^~~~~~~~~~~~~~
fish.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0;i<size(dp[n-1]);i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
27072 KB |
Output is correct |
| 2 |
Correct |
50 ms |
29636 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23860 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23840 KB |
Output is correct |
| 5 |
Correct |
139 ms |
41356 KB |
Output is correct |
| 6 |
Correct |
116 ms |
42580 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
9820 KB |
Output is correct |
| 2 |
Incorrect |
82 ms |
31956 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23900 KB |
Output is correct |
| 3 |
Incorrect |
47 ms |
25408 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '21261871744627' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
1 ms |
9648 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
9820 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
1 ms |
9648 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
9820 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
1 ms |
9648 KB |
Output is correct |
| 3 |
Incorrect |
2 ms |
9820 KB |
1st lines differ - on the 1st token, expected: '4044', found: '2022' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
23896 KB |
Output is correct |
| 2 |
Correct |
21 ms |
23900 KB |
Output is correct |
| 3 |
Incorrect |
47 ms |
25408 KB |
1st lines differ - on the 1st token, expected: '21261825233649', found: '21261871744627' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
27072 KB |
Output is correct |
| 2 |
Correct |
50 ms |
29636 KB |
Output is correct |
| 3 |
Correct |
22 ms |
23860 KB |
Output is correct |
| 4 |
Correct |
22 ms |
23840 KB |
Output is correct |
| 5 |
Correct |
139 ms |
41356 KB |
Output is correct |
| 6 |
Correct |
116 ms |
42580 KB |
Output is correct |
| 7 |
Correct |
1 ms |
9820 KB |
Output is correct |
| 8 |
Incorrect |
82 ms |
31956 KB |
1st lines differ - on the 1st token, expected: '40604614618209', found: '40604944491929' |
| 9 |
Halted |
0 ms |
0 KB |
- |
