結果

問題 No.1150 シュークリームゲーム（Easy）
コンテスト
ユーザー Shibuyap
提出日時 2020-08-07 23:08:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 56 ms / 2,000 ms
コード長 6,676 bytes
コンパイル時間 3,323 ms
コンパイル使用メモリ 194,432 KB
最終ジャッジ日時 2025-01-12 18:02:25
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using namespace std;
typedef pair<int,int> P;
typedef long long int ll;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}

const int MAX_N = 1 << 19;

// セグメント木を持つグローバル配列
ll nn, dat[2 * MAX_N - 1];
ll INF = 1001001001001001001;
// 初期化
void init(int n_){
    // n_が小さいときの変な挙動を防ぐ
    if(n_ < 10)n_ = 10;
    // 簡単のため要素数を2のべき乗に
    nn = 1;
    while(nn < n_)nn *= 2;

    // 全ての値をINT_MAXに
    for(int i = 0; i < 2 * nn - 1; i++)dat[i] = INF;
}

// k番目の値(0-indexed)をaに変更
void update(int k, ll a){
    // 葉の接点
    k += nn - 1;
    dat[k] = a;
    // 登りながら更新
    while(k > 0){
        k = (k - 1) / 2;
        dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
    }
}

// [a,b)の最小値を求める
// 後ろのほうの引数は、計算の簡単のための引数。
// kは節点の番号、l, rはその節点が[l, r)に対応づいていることを表す。
// したがって、外からはquery(a, b, 0, 0, nn)として呼ぶ。
ll query(int a, int b, int k, int l, int r){
    // [a, b)と[l, r)が交差しなければ、INT_MAX
    if (r <= a || b <= l)return INF;

    // [a, b)が[l, r)を完全に含んでいれば、この節点の値
    if (a <= l && r <= b)return dat[k];
    else {
        // そうでなければ、2つの子の最小値
        ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return min(vl, vr);
    }
}


int main(){
    int n, s, t;
    cin >> n >> s >> t;
    s--; t--;

    init(n*2);

    ll a[n];
    ll sum = 0;
    rep(i,n){
        cin >> a[i];
        sum += a[i];
    } 
    int f[n] = {};
    ll x = 0, y = 0;
    int ss = s, tt = t;
    if(n % 2 == 1){
        if(s < t){
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+n-1)%n;
            }
            ss = (s+n-1)%n;
            tt = (t+1)%n;
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+n-1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+1)%n;
            }
        }else{
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+n-1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+1)%n;
            }
            ss = (s+1)%n;
            tt = (t+n-1)%n;
            while(true){
                if(f[ss])break;
                x += a[ss];
                f[ss] = 1;
                ss = (ss+1)%n;
                if(f[tt])break;
                y += a[tt];
                f[tt] = 1;
                tt = (tt+n-1)%n;
            }
        }
    }else{
        if(abs(s-t)%2==1){
            if(s < t){
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                ss = (s+n-1)%n;
                tt = (t+1)%n;
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
            }else{
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                ss = (s+1)%n;
                tt = (t+n-1)%n;
                while(true){
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
            }
        }else{
            ll aa, bb;
            if(s < t){
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                aa = a[ss];
                ss = (s+n-1)%n;
                tt = (t+1)%n;
                while(true){
                    if(ss==tt)break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                bb = a[ss];
            }else{
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+n-1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+1)%n;
                }
                aa = a[ss];
                ss = (s+1)%n;
                tt = (t+n-1)%n;
                while(true){
                    if(ss == tt) break;
                    if(f[ss])break;
                    x += a[ss];
                    f[ss] = 1;
                    ss = (ss+1)%n;
                    if(f[tt])break;
                    y += a[tt];
                    f[tt] = 1;
                    tt = (tt+n-1)%n;
                }
                bb = a[ss];
            }
            x += max(aa,bb);
            y += min(aa,bb);
        }
    }

    cout << x - y << endl;
    return 0;
}
0