AT_arc096_b 题解

ikunTLE · 2025-10-26 17:11:23 · 题解

思路

不难发现以下几个性质：

• 无论先往哪个方向走，都会沿着当前方向走，中途可能会折返向反方向走一段更远的距离。
• 离开时一定是吃完一个寿司马上离开，不会再走多余的步数。

先考虑考虑顺时针走，可以使用前缀和的思路，处理一步步走到点 x_i 的价值：p_i\gets p_{i-1}-(x_i-x_{i-1})+v_i。同时令 f_i=\max_{j=1}^i p_i，表示走到 x_i 之前的一个点能获得的最大价值。同理也可以处理逆时针的后缀和。

但是这种做法目前只能做到一个方向走到底的答案，答案也有可能是存在一个折返产生的。最简单的方法是破环成链：从原点定位下标 N，逆时针的后缀和下表从 0 到 N-1，顺时针的前缀和从 N+1 到 2N。

然后从左到右一次处理包含 N-1 个点的区间贡献，注意这个贡献要减去两侧点到原点的较小距离。

AC CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){int x=0;char f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;}
const int N=2e5+10;
struct node{
    int pos,val;
}a[N];
int p[N],f[N];
signed main(){
    int n=read(),c=read();
    for(int i=1;i<=n;++i){
        int pos=read(),val=read();
        a[i-1]={c-pos,val};
        a[n+i]={pos,val};
    }
    for(int i=n+1;i<=n*2;++i){
        p[i]=p[i-1]-(a[i].pos-a[i-1].pos)+a[i].val;
        f[i]=max(f[i-1],p[i]);
    }
    for(int i=n-1;i>=0;--i){
        p[i]=p[i+1]-(a[i].pos-a[i+1].pos)+a[i].val;
        f[i]=max(f[i+1],p[i]);
    }
    int res=0;
    for(int i=0;i<=n;++i)
        res=max(res,f[i]+f[n+i]-min(abs(a[i].pos),abs(a[n+i].pos)));
    printf("%lld\n",res);
    return 0;
}