| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 863454 |
2023-10-20T11:37:31 Z |
neki |
Catfish Farm (IOI22_fish) |
C++17 |
|
0 ms |
0 KB |
#include <bits/stdc++.h>
#include "fish.h"
#define ll long long
#define vc vector
using namespace std;
ll max_weights(int N, int M, vc<int> X, vc<int> Y, vc<int> W) {
vc<ll> ind(M); for(ll i=0;i<M;++i) ind[i]=i;
sort(ind.begin(),ind.end(),[&](ll a,ll b){return Y[a]<Y[b];});
vc<vc<pair<ll, ll>>> f(N);
vc<vc<ll>> rel(N, vc<ll>(1, -1)), dpm(N, vc<ll>(1, 0)), dpv(N, vc<ll>(1, 0)), dpn(N, vc<ll>(1, 0));
for(auto i: ind){
f[X[i]].emplace_back(Y[i], W[i]);
if(X[i]-1>=0) rel[X[i]-1].push_back(Y[i]),dpn[X[i]-1].push_back(0),dpm[X[i]-1].push_back(0),dpv[X[i]-1].push_back(0);
if(X[i]+1<N) rel[X[i]+1].push_back(Y[i]),dpn[X[i]+1].push_back(0),dpm[X[i]+1].push_back(0),dpv[X[i]+1].push_back(0);
}
for(ll i=0;i<N;++i){
if(i-2>=0){
for(ll j=0, prej=0, c=0, pp=0, mm=0;j<(ll)rel[i].size();++j){
while(pp<(ll)rel[i-2].size()&&rel[i-2][pp]<=rel[i][j])mm=max(mm, max(dpv[i-2][pp], dpm[i-2][pp])),++pp;
while(prej<(ll)f[i-1].size()&&f[i-1][prej].first<=rel[i][j])c+=f[i-1][prej++].second;
dpv[i][j]=max(dpv[i][j],mm+c);
dpm[i][j]=max(dpm[i][j],mm+c);
}
for(ll j=(ll)rel[i].size()-1, pp=(ll)rel[i-2].size(), mm=0;j>=0;--j){
while(pp-1>=0&&rel[i-2][pp-1]>=rel[i][j])mm=max(mm, dpn[i-2][--pp]);
dpv[i][j]=max(dpv[i][j],mm);
dpm[i][j]=max(dpm[i][j],mm);
}
}
if(i-1>=0){
for(ll j=0, prej=0, pf=0, mm=0;j<(ll)rel[i].size();++j){
while(1){
if(prej<(ll)rel[i-1].size()&&rel[i-1][prej]<=rel[i][j]&&(!(pf<(ll)f[i-1].size()) || rel[i-1][prej]<f[i-1][pf].first))mm=max(mm, dpm[i-1][prej++]);
else if(pf<(ll)f[i-1].size()&&f[i-1][pf].first<=rel[i][j])mm+=f[i-1][pf++].second;
else break;
}
dpm[i][j]=max(dpm[i][j], mm);
}
ll mm=max(dpn[i-1].begin, dpn[i-1].end());
for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
while(nas<(ll)f[i].size()&&f[i][nas].first<=rel[i][j])c+=f[i][nas++].second;
dpv[i][j]=max({dpv[i][j],dpm[i][j], mm-c});
}
}
if(i+1<N){
for(ll j=0, nas=0, c=0;j<(ll)rel[i].size();++j){
while(nas<(ll)f[i+1].size()&&f[i+1][nas].first<=rel[i][j])c+=f[i+1][nas++].second;
dpn[i][j]=max(dpn[i][j],max(dpv[i][j], dpm[i][j])+c);
}
}
}
ll ans=0;
for(ll i=0;i<N;++i){
for(ll j=0;j<(ll)rel[i].size();++j)ans=max({ans, dpn[i][j], dpv[i][j], dpm[i][j]});
}
return ans;
}
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:45:53: error: no matching function for call to 'max(<unresolved overloaded function type>, std::vector<long long int>::iterator)'
45 | ll mm=max(dpn[i-1].begin, dpn[i-1].end());
| ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
from /usr/include/c++/10/cmath:1927,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
from fish.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'constexpr const _Tp& std::max(const _Tp&, const _Tp&) [with _Tp = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]'
254 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:20: note: no known conversion for argument 1 from '<unresolved overloaded function type>' to 'const __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >&'
254 | max(const _Tp& __a, const _Tp& __b)
| ~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
300 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: template argument deduction/substitution failed:
fish.cpp:45:53: note: candidate expects 3 arguments, 2 provided
45 | ll mm=max(dpn[i-1].begin, dpn[i-1].end());
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from fish.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
3480 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: template argument deduction/substitution failed:
fish.cpp:45:53: note: mismatched types 'std::initializer_list<_Tp>' and 'std::vector<long long int>::const_iterator (std::vector<long long int>::*)() const noexcept'
45 | ll mm=max(dpn[i-1].begin, dpn[i-1].end());
| ^
fish.cpp:45:53: note: mismatched types 'std::initializer_list<_Tp>' and 'std::vector<long long int>::iterator (std::vector<long long int>::*)() noexcept'
fish.cpp:45:53: note: candidate expects 1 argument, 2 provided
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from fish.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
3486 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: template argument deduction/substitution failed:
fish.cpp:45:53: note: mismatched types 'std::initializer_list<_Tp>' and 'std::vector<long long int>::const_iterator (std::vector<long long int>::*)() const noexcept'
45 | ll mm=max(dpn[i-1].begin, dpn[i-1].end());
| ^
fish.cpp:45:53: note: mismatched types 'std::initializer_list<_Tp>' and 'std::vector<long long int>::iterator (std::vector<long long int>::*)() noexcept'
fish.cpp:45:53: note: couldn't deduce template parameter '_Tp'
