#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define st first
#define nd second
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
int inf=1000000007;
ll infl=1000000000000000007;
const int N=100007;
set<int>points[N];
unordered_map<int,ll>DP[2][N];
unordered_map<int,ll>L[N];
unordered_map<int,ll>R[N];
unordered_map<int,ll>M[N];
vector<pair<int,int>>V[N];
ll max_weights(int n,int m,vector<int>X,vector<int>Y,vector<int>W)
{
for(int i=0;i<m;i++)
{
X[i]++;
Y[i]++;
points[X[i]].insert(Y[i]-1);
points[X[i]-1].insert(Y[i]);
points[X[i]+1].insert(Y[i]);
V[X[i]].pb({Y[i],W[i]});
}
for(int i=1;i<=n;i++)
{
points[i].insert(0);
sort(all(V[i]));
}
for(int i=1;i<=n;i++)
{
vector<pair<int,int>>P;
for(auto [y,c]:V[i-1]) P.pb({y,c});
for(auto y:points[i]) P.pb({y,inf});
sort(all(P));
ll sum=0;
for(auto [y,c]:P)
{
if(c==inf) L[i][y]=sum;
else sum+=c;
}
P.clear();
for(auto [y,c]:V[i+1]) P.pb({y,c});
for(auto y:points[i]) P.pb({y,infl});
sort(all(P));
sum=0;
for(auto [y,c]:P)
{
if(c==inf) R[i][y]=sum;
else sum+=c;
}
P.clear();
for(auto [y,c]:V[i]) P.pb({y,c});
for(auto y:points[i]) P.pb({y,infl});
sort(all(P));
sum=0;
for(auto [y,c]:P)
{
if(c==inf) M[i][y]=sum;
else sum+=c;
}
}
for(auto x:points[1]) DP[1][1][x]=-infl;
ll ans=0;
for(int i=2;i<=n;i++)
{
vector<pair<int,int>>P;
for(auto y:points[i-2]) P.pb({y,0});
for(auto y:points[i]) P.pb({y,1});
sort(all(P));
ll mx=0;
for(auto [y,c]:P)
{
if(c==0) mx=max({mx,DP[0][i-2][y],DP[1][i-2][y]});
else DP[0][i][y]=max(DP[0][i][y],mx+L[i][y]);
}
reverse(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c==0) mx=max(mx,max(DP[0][i-2][y],DP[1][i-2][y])+R[i-2][y]);
else DP[0][i][y]=max(DP[0][i][y],mx);
}
P.clear();
for(auto y:points[i-1]) P.pb({y,0});
for(auto y:points[i]) P.pb({y,1});
sort(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c==0) mx=max(mx,DP[0][i-1][y]-M[i-1][y]);
else DP[0][i][y]=max(DP[0][i][y],mx+L[i][y]);
}
reverse(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c==0) mx=max(mx,max(DP[0][i-1][y],DP[1][i-1][y])+R[i-1][y]);
else DP[1][i][y]=max(DP[1][i][y],mx-M[i][y]);
}
for(auto y:points[i]) ans=max({ans,DP[0][i][y],DP[1][i][y]});
}
return ans;
}
int main()
{
cout<<max_weights(5, 4,{0, 1, 4, 3},{2, 1, 4, 3},{5, 2, 1, 3})<<endl;
return 0;
}
Compilation message
/usr/bin/ld: /tmp/ccxldgA3.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccehyQs3.o:fish.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
