This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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>S[N];
vector<int>points[N];
vector<ll>DP[2][N];
vector<ll>L[N];
vector<ll>R[N];
vector<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]++;
S[X[i]].insert(Y[i]-1);
S[X[i]-1].insert(Y[i]);
S[X[i]+1].insert(Y[i]);
V[X[i]].pb({Y[i],W[i]});
}
for(int i=1;i<=n;i++)
{
S[i].insert(0);
sort(all(V[i]));
for(auto x:S[i]) points[i].pb(x);
DP[0][i].resize(sz(points[i]),0);
DP[1][i].resize(sz(points[i]),0);
L[i].resize(sz(points[i]),0);
R[i].resize(sz(points[i]),0);
M[i].resize(sz(points[i]),0);
}
for(int i=1;i<=n;i++)
{
vector<pair<pair<int,int>,int>>P;
for(auto [y,c]:V[i-1]) P.pb({{y,-c},1});
for(auto [y,c]:V[i]) P.pb({{y,-c},2});
for(auto [y,c]:V[i+1]) P.pb({{y,-c},3});
for(int j=0;j<sz(points[i]);j++) P.pb({{points[i][j],j},0});
sort(all(P));
ll sum1=0,sum2=0,sum3=0;
for(auto [y,c]:P)
{
if(c==0)
{
L[i][y.nd]=sum1;
M[i][y.nd]=sum2;
R[i][y.nd]=sum3;
}
else if(c==1) sum1+=(ll)-y.nd;
else if(c==2) sum2+=(ll)-y.nd;
else sum3+=(ll)-y.nd;
}
}
for(int i=0;i<sz(points[1]);i++) DP[1][1][i]=-infl;
ll ans=0;
for(int i=2;i<=n;i++)
{
vector<pair<int,int>>P;
for(int j=0;j<sz(points[i-2]);j++) P.pb({points[i-2][j],-j-1});
//for(auto y:points[i-2]) P.pb({y,0});
for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
//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][-c-1],DP[1][i-2][-c-1]});
else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
}
reverse(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c<0) mx=max(mx,max(DP[0][i-2][-c-1],DP[1][i-2][-c-1])+R[i-2][-c-1]);
else DP[0][i][c]=max(DP[0][i][c],mx);
}
P.clear();
for(int j=0;j<sz(points[i-1]);j++) P.pb({points[i-1][j],-j-1});
for(int j=0;j<sz(points[i]);j++) P.pb({points[i][j],j});
sort(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c<0) mx=max(mx,DP[0][i-1][-c-1]-M[i-1][-c-1]);
else DP[0][i][c]=max(DP[0][i][c],mx+L[i][c]);
}
reverse(all(P));
mx=0;
for(auto [y,c]:P)
{
if(c<0) mx=max(mx,max(DP[0][i-1][-c-1],DP[1][i-1][-c-1])+R[i-1][-c-1]);
else DP[1][i][c]=max(DP[1][i][c],mx-M[i][c]);
}
for(int j=0;j<sz(points[i]);j++) ans=max({ans,DP[0][i][j],DP[1][i][j]});
}
return ans;
}
/*
int main()
{
int n=100000,m=100000;
//cin>>n>>m;
vector<int>X(m),Y(m),C(m);
for(int i=0;i<m;i++)
{
//cin>>X[i]>>Y[i]>>C[i];
X[i]=rand()%n;
Y[i]=rand()%n;
C[i]=rand()%1000000+1;
}
cout<<max_weights(n,m,X,Y,C)<<endl;
return 0;
}*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |