#include<bits/stdc++.h>
using namespace std;
int s[100005],a[100005],b[100005],k;
int f[100005],g[100005],ans;
void work(int t,int hd,int tl)
{
if(t==1)
{
if((tl-hd+1)%2==0)return;
int Min=1e9+1;
for(int i=hd;i<=tl;i+=2)Min=min(Min,b[i]);
for(int i=hd+1;i<=tl;i+=2)if(a[i+1]-a[i-1]<=k)Min=min(Min,b[i]);
ans+=Min;return;
}
f[tl]=b[tl];f[tl-1]=0;g[tl]=0;g[tl-1]=max(b[tl-1],b[tl]);
for(int i=tl-2;i>=hd;i--)
{
g[i]=f[i+1];
if((s[i]-i-1)%2==1)g[i]=max(g[i],f[s[i]]+b[i]);
else if(a[s[i]]-a[s[i]-1]<=k)
{
g[i]=max(g[i],f[s[i]+1]+b[i]);
if(a[s[i]+1]-a[s[i]-1]<=k)g[i]=max(g[i],g[s[i]]+b[i]);
}
f[i]=f[i+2];
if((s[i]-i-1)%2==0)f[i]=max(f[i],f[s[i]]+b[i]);
else if(a[s[i]]-a[s[i]-1]<=k)
{
f[i]=max(f[i],f[s[i]+1]+b[i]);
if(a[s[i]+1]-a[s[i]-1]<=k)f[i]=max(f[i],g[s[i]]+b[i]);
}
if(a[i+2]-a[i]<=k)
if((s[i+1]-i-2)%2==1)f[i]=max(f[i],f[s[i+1]]+b[i+1]);
else if(a[s[i+1]]-a[s[i+1]-1]<=k)
{
f[i]=max(f[i],f[s[i+1]+1]+b[i+1]);
if(a[s[i+1]+1]-a[s[i+1]-1]<=k)f[i]=max(f[i],g[s[i+1]]+b[i+1]);
}
}
ans+=f[hd];return;
}
int main()
{
int t,n;scanf("%d%d%d",&t,&n,&k);
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
a[n+1]=2e9+1;int pt=2;for(;pt<=n+1&&a[pt]-a[1]<=k;pt++);s[1]=pt;
for(int i=2;i<=n;i++){for(;pt<=n+1&&a[pt]-a[i]<=k;pt++);s[i]=pt;}
int h=1;
for(int i=1;i<=n;)
{
while(i<n&&a[i+1]-a[i]<=k)i++;
work(t,h,i);
h=++i;
}
cout<<ans<<endl;
}
The Answer to T904(Paired_Up) 来源于王志超大牛
2023-06-04 20:24:39 By yyhs_luyicheng