結果
| 問題 | 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 |
ソースコード
#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_MAXif (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;}