組み合わせる(ARC096D - Static Sushi)

atcoder.jp

まず、摂取カロリーを最大化したいので、当然前を通った寿司をスルーするということはできません。よって移動方法を考えることになります。。
また、スルーしないという条件より、最低でも全ての寿司の前を通った時には店を出なければいけませんし、歩くとカロリーを消費することから方向を変えたり店を出る地点は寿司の前だけに限られます。
もっと考えると、同じ道を行ったり来たりするのは効率が悪いので、そのようなことはせいぜい一回しか起こりません。行きたい寿司のうち最も原点から離れている寿司まで行って、そこで終わるか、反対側の寿司を取ったほうがいいときは反転して、そこで終わりです。

よって、まず左回転と右回転でそれぞれi番目の寿司まで行った時の摂取カロリー-消費カロリーの値を保持しておいて、それの組み合わせを考えます。
全ての組み合わせは最初に行く回転の方向まで考えるとn(n-1)通りありますがそれでは間に合わないです。左回転でiまで行った時右回転でどこまでいけば良いのかは、i+1以降で最初に求めた摂取カロリー-消費カロリーの値が一番大きくなるところでいいです。そんな感じで右回転始まりについても求めて、終わりです。

まあ簡単だったかな
というより500点問題以下にはこういう順当に考察して数え上げればいいだけのものが多いので、水色になるのはプログラミングになれれば出来そう（「なるためにやったこと」的アドバイス）

#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>

 
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define LLIandI pair<long long int , int>
#define ll long long
int main(void){
    int N;
    long long int C;
    scanf("%d %lld",&N,&C);
    long long int x[100004];
    long long int v[100004];
    long long int v_inc[100004];
    long long int v_inc_max[100004];
    long long int v_dec[100004];
    long long int v_dec_max[100004];
    rep(i,N){
        scanf("%lld %lld",&x[i],&v[i]);
        i==0 ? (v_inc[i]=v[i]-x[i]) : (v_inc[i]=v_inc[i-1]+v[i]-(x[i]-x[i-1]) );
        i==0 ? (v_inc_max[i]= v_inc[i]) : (v_inc_max[i]=max(v_inc[i],v_inc_max[i-1]));
    }
    rep(i,N){
        int j=N-1-i;
        i==0?(v_dec[j]=v[j]-(C-x[j])) : (v_dec[j]=v_dec[j+1]+v[j]-(x[j+1]-x[j]) );
        i==0?(v_dec_max[j]= v_dec[j]) : (v_dec_max[j]=max(v_dec[j],v_dec_max[j+1]));
    }
    
    long long int ans=0;//動かないという選択肢
    rep(i,N){
        if(i==N-1 || v_dec_max[i+1]<=x[i]){ans=max(ans,v_inc[i]);continue;}//方向転換しないのがベスト
        else{ans=max(ans,v_inc[i]-x[i]+v_dec_max[i+1]);continue;}//方向転換するのがベスト
    }
    //from decriment
    rep(i,N){
        int j=N-1-i;
        if(j==0||v_inc_max[j-1]<=C-x[j]){ans=max(ans,v_dec[j]);continue;}
        else{ans=max(ans,v_dec[j]-(C-x[j])+v_inc_max[j-1]);continue;}//方向転換するのがベスト
    }
    printf("%lld\n",ans);
}