#include "bits/stdc++.h"
#include "fish.h"
//#define int64_t long long
#define all(v) v.begin() , v.end()
#define sz(a) (int64_t)a.size()
using namespace std;
const int64_t INF = 1e15;
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
int64_t n,m,ans=0;
n=N,m=M;
vector<array<int64_t,3>> ar(m);
for(int64_t i=0;i<m;i++){
ar[i][0]=X[i];
ar[i][1]=Y[i];
ar[i][2]=W[i];
ar[i][0]++;
}
vector<int64_t> consider[n+5];
vector<array<int64_t,2>> pre[n+5];
vector<array<int64_t,2>> fish[n+5];
for(int64_t i=0;i<m;i++){
if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
}
for(int64_t i=0;i<=n;i++){
consider[i].push_back(0);
sort(all(consider[i]));
consider[i].erase(unique(all(consider[i])),consider[i].end());
}
for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
for(int64_t i=1;i<=n;i++){
fish[i].push_back({0,0});
sort(all(fish[i]));
int64_t64_t cur=0;
for(auto x:fish[i]){
cur+=x[1];
pre[i].push_back({x[0],cur});
}
}
vector<int64_t> dp[n+5][2];
for(int64_t i=0;i<=n;i++){
dp[i][0].assign(sz(consider[i]),0);
dp[i][1].assign(sz(consider[i]),0);
}
auto get_sum=[&](int64_t i,int64_t j)->int64_t{
if(i<1 || i>n) return 0;
array<int64_t,2> bs={j+1,-1};
int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
if(it>0) return pre[i][it-1][1];
return 0;
};
for(int64_t i=1;i<=n;i++){
// calc increasing dp
vector<array<int64_t,2>> v;
int64_t cur=0;
for(int64_t j=0;j<sz(dp[i-1][0]);j++){
cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
v.push_back({consider[i-1][j],cur});
}
auto get_val=[&](int64_t u,int64_t t)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(v),bs)-v.begin();
if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
return -INF;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
int64_t val=get_sum(i-1,u)+get_val(u,1);
dp[i][0][j]=max(dp[i][0][j],val);
}
// calc decrasing dp
v.clear();
cur=0;
for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
cur=max(cur,dp[i-1][1][j]);
v.push_back({consider[i-1][j],cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(dp[i][1]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
}
if(i>=2){ // new block
vector<array<int64_t,2>> arka[2];
cur=0;
for(int64_t j=0;j<sz(consider[i-2]);j++){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]);
cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
arka[0].push_back({u,cur});
}
cur=0;
for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
cur=max(cur,dp[i-2][1][j]);
arka[1].push_back({u,cur});
}
reverse(all(arka[1]));
auto get_kucuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
if(it>0) return arka[0][it-1][1];
return -INF;
};
auto get_buyuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
if(it<sz(arka[1])) return arka[1][it][1];
return -INF;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
}
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
}
}
// inc to dec
v.clear();
cur=0;
//cout << "kur: " << '\n';
for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
int64_t u=consider[i-1][j];
//cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
v.push_back({u,cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
//cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
//cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
//cout << dp[i][1][j] << '\n';
}
for(int64_t j=0;j<sz(consider[i]);j++){
//cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
//cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
ans=max(ans,dp[i][1][j]);
}
}
return ans;
}
/*void _(){
int64_t n,m,ans=0;
cin >> n >> m;
vector<array<int64_t,3>> ar(m);
for(int64_t i=0;i<m;i++){
cin >> ar[i][0] >> ar[i][1] >> ar[i][2];
ar[i][0]++;
}
vector<int64_t> consider[n+5];
vector<array<int64_t,2>> pre[n+5];
vector<array<int64_t,2>> fish[n+5];
for(int64_t i=0;i<m;i++){
if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
}
for(int64_t i=0;i<=n;i++){
consider[i].push_back(0);
sort(all(consider[i]));
consider[i].erase(unique(all(consider[i])),consider[i].end());
}
for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
for(int64_t i=1;i<=n;i++){
fish[i].push_back({0,0});
sort(all(fish[i]));
int64_t cur=0;
for(auto x:fish[i]){
cur+=x[1];
pre[i].push_back({x[0],cur});
}
}
vector<int64_t> dp[n+5][2];
for(int64_t i=0;i<=n;i++){
dp[i][0].assign(sz(consider[i]),0);
dp[i][1].assign(sz(consider[i]),0);
}
auto get_sum=[&](int64_t i,int64_t j)->int64_t{
if(i<1 || i>n) return 0;
array<int64_t,2> bs={j+1,-1};
int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
if(it>0) return pre[i][it-1][1];
return 0;
};
for(int64_t i=1;i<=n;i++){
// calc increasing dp
vector<array<int64_t,2>> v;
int64_t cur=0;
for(int64_t j=0;j<sz(dp[i-1][0]);j++){
cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
v.push_back({consider[i-1][j],cur});
}
auto get_val=[&](int64_t u,int64_t t)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(v),bs)-v.begin();
if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
return -INF;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
int64_t val=get_sum(i-1,u)+get_val(u,1);
dp[i][0][j]=max(dp[i][0][j],val);
//cout << "hm0: " << i << ' ' << j << ' ' << u << '\n';
//cout << dp[i][0][j] << '\n';
}
// calc decrasing dp
v.clear();
cur=0;
for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
cur=max(cur,dp[i-1][1][j]);
v.push_back({consider[i-1][j],cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(dp[i][1]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
//cout << "hm1: " << i << ' ' << j << ' ' << u << '\n';
//cout << dp[i][1][j] << '\n';
}
if(i>=2){ // new block
vector<array<int64_t,2>> arka[2];
cur=0;
for(int64_t j=0;j<sz(consider[i-2]);j++){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]);
cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
arka[0].push_back({u,cur});
}
cur=0;
for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
cur=max(cur,dp[i-2][1][j]);
arka[1].push_back({u,cur});
}
reverse(all(arka[1]));
auto get_kucuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
if(it>0) return arka[0][it-1][1];
return -INF;
};
auto get_buyuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
if(it<sz(arka[1])) return arka[1][it][1];
return -INF;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
//cout << "b0: " << i << ' ' << j << ' ' << u << '\n';
//cout << dp[i][0][j] << '\n';
}
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
//cout << "b1: " << i << ' ' << j << ' ' << u << '\n';
//cout << dp[i][1][j] << '\n';
}
}
// inc to dec
v.clear();
cur=0;
//cout << "kur: " << '\n';
for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
int64_t u=consider[i-1][j];
//cout << i << ' ' << j << ' ' << dp[i-1][0][j] << ' ' << get_sum(i,u) << '\n';
cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
v.push_back({u,cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
//cout << "hmm: " << i << ' ' << j << ' ' << u << '\n';
//cout << get_val(u,0) << ' ' << get_sum(i,u) << ' ' << get_sum(i+1,u) << '\n';
//cout << dp[i][1][j] << '\n';
}
for(int64_t j=0;j<sz(consider[i]);j++){
//cout << "check: " << i << ' ' << j << ' ' << consider[i][j] << '\n';
//cout << dp[i][0][j] << ' ' << dp[i][1][j] << '\n';
ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
ans=max(ans,dp[i][1][j]);
}
}
cout << ans << '\n';
}
int64_t32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int64_t tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/
Compilation message
fish.cpp: In function 'long long int max_weights(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
fish.cpp:39:5: error: 'int64_t64_t' was not declared in this scope; did you mean 'int_fast64_t'?
39 | int64_t64_t cur=0;
| ^~~~~~~~~~~
| int_fast64_t
fish.cpp:41:7: error: 'cur' was not declared in this scope
41 | cur+=x[1];
| ^~~
fish.cpp:42:34: error: no matching function for call to 'std::vector<std::array<long int, 2> >::push_back(<brace-enclosed initializer list>)'
42 | pre[i].push_back({x[0],cur});
| ^
In file included from /usr/include/c++/10/vector:67,
from /usr/include/c++/10/functional:62,
from /usr/include/c++/10/pstl/glue_algorithm_defs.h:13,
from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from fish.cpp:1:
/usr/include/c++/10/bits/stl_vector.h:1187:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(const value_type&) [with _Tp = std::array<long int, 2>; _Alloc = std::allocator<std::array<long int, 2> >; std::vector<_Tp, _Alloc>::value_type = std::array<long int, 2>]'
1187 | push_back(const value_type& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1187:35: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::array<long int, 2>&'}
1187 | push_back(const value_type& __x)
| ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_vector.h:1203:7: note: candidate: 'void std::vector<_Tp, _Alloc>::push_back(std::vector<_Tp, _Alloc>::value_type&&) [with _Tp = std::array<long int, 2>; _Alloc = std::allocator<std::array<long int, 2> >; std::vector<_Tp, _Alloc>::value_type = std::array<long int, 2>]'
1203 | push_back(value_type&& __x)
| ^~~~~~~~~
/usr/include/c++/10/bits/stl_vector.h:1203:30: note: no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::vector<std::array<long int, 2> >::value_type&&' {aka 'std::array<long int, 2>&&'}
1203 | push_back(value_type&& __x)
| ~~~~~~~~~~~~~^~~
