#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
using lint=long long;
const int lim=3e3+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});
/*
cerr<<"my i is "<<i<<"\n";
cerr<<(rp-pref[i].begin())<<" rp\n";
cerr<<r<<" :: ";
cerr<<rp->first<<" "<<rp->second<<"\n";
*/
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});
sort(pref[i].begin(),pref[i].end());
for(int j=0;j<size(pref[i]);j++){
inds[i].push_back(pref[i][j].first);
}
for(int j=1;j<size(pref[i]);j++){
pref[i][j].second+=pref[i][j-1].second;
}
/*
cerr<<"pref "<<i<<" {\n";
for(auto[f,s]:pref[i]){
cerr<<"\b"<<f<<" "<<s<<"\n";
}cerr<<"}\n";
*/
}
dp[0].resize(pref[0].size());
up[0].resize(pref[0].size());
for(int i=0;i<size(dp[0]);i++){
dp[0][i]=pref[0][i].second;
up[0][i]=0;
}
for(int i=1;i<n;i++){
dp[i].resize(pref[i].size());
up[i].resize(pref[i].size());
lint max1=0;
int pp=0;
for(int j=0;j<size(dp[i]);j++){
/*
cerr<<"ok\n";
cerr<<j<<" "<<size(dp[i])<<"\n";
cerr<<pp<<" "<<size(up[i-1])<<"\n";
*/
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++;
}
/*
cerr<<"bruh\n";
cerr<<size(dp[i])<<" "<<size(up[i])<<" "<<size(inds[i])<<"\n";
cerr<<j<<"\n";
*/
dp[i][j]=max(dp[i][j],max1+p(i-1,0,inds[i][j])+p(i+1,0,inds[i][j]));
//cerr<<"??\n";
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()){
//cerr<<"right here\n";
p--;
//cerr<<"it moved\n";
up[i][j]=max(up[i][j],dp[i-1][p-inds[i-1].begin()]);
//cerr<<"oops\n";
}
//cerr<<"ok i guess\n";
}
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:40: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]
40 | for(int j=0;j<size(pref[i]);j++){
| ~^~~~~~~~~~~~~~
fish.cpp:43: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]
43 | for(int j=1;j<size(pref[i]);j++){
| ~^~~~~~~~~~~~~~
fish.cpp:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(int i=0;i<size(dp[0]);i++){
| ~^~~~~~~~~~~~
fish.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int j=0;j<size(dp[i]);j++){
| ~^~~~~~~~~~~~
fish.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while(pp<size(up[i-1])&&inds[i-1][pp]<=inds[i][j]){
| ~~^~~~~~~~~~~~~~
fish.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int i=0;i<size(dp[n-1]);i++){
| ~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 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 |
Runtime error |
1 ms |
1372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
604 KB |
1st lines differ - on the 1st token, expected: '3', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
1372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
19 ms |
9160 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
