fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. typedef long long ll;
  4. using namespace std;
  5. ll n , s;
  6. ll a[400005];
  7. const ll inf = 1e16;
  8. set<ll> S;
  9. ll d[400005];
  10. int main()
  11. {
  12.         cin >> n >> s;
  13.         ll mmm = 1e14;
  14.         for(ll i=0;i<n;i++) {
  15.                 cin >> a[i];
  16.                 mmm = min(mmm , a[i]);
  17.                 S.insert(i);
  18.                 S.insert(i + n);
  19.         }
  20.         if(n == 1) {
  21.                 cout << "0\n"; return 0;
  22.         }
  23.         if(n == 2) {
  24.                 cout << mmm << endl; return 0;
  25.         }
  26.         for(ll i=n;i<n+n;i++) {
  27.                 a[i] = a[i - n];
  28.         }
  29.         for(ll i=0;i<n+n;i++) {
  30.                 if(i) d[i] = d[i-1];
  31.                 d[i] += a[i];
  32.         }
  33.         ll cur = s-1;
  34.         ll ans = 0;
  35.         while(S.size() > 2) {
  36.  
  37.                 auto nxt = S.lower_bound(cur);
  38.                 auto prv = S.lower_bound(cur + n);
  39.                 nxt++;
  40.                 prv--;
  41.                 ll NN = 0;
  42.                 NN = *nxt;
  43.                 ll PP = *prv;
  44.                 S.erase(S.find(cur));
  45.                 S.erase(S.find(cur+n));
  46.                 ll aage = 1e9;
  47.                 ll piche = 1e9;
  48.                 if(NN>0) aage = d[NN-1];
  49.                 if(cur>0) aage -= d[cur - 1];
  50.                 if(cur+n-1>0)piche = d[cur+n-1];
  51.                 if(PP > 0) piche -= d[PP-1];
  52.                 if(aage < piche) {
  53.                         ans += aage;
  54.                         ll RA = NN;
  55.                         if(RA >= n) RA -= n;
  56.                         cur = RA;
  57.                 }else if(aage > piche){
  58.                         ans += piche;
  59.                         ll RB = PP;
  60.                         if(RB >= n) RB -= n;
  61.                         cur = RB;
  62.                 }else {
  63.                         ll RA = NN;
  64.                         if(RA >= n) RA -= n;
  65.                         ll RB = PP;
  66.                         if(RB >= n) RB -= n;
  67.                         if(RA < RB) {
  68.                                 cur = RA;
  69.                                 ans += aage;
  70.                         }else {
  71.                                 cur = RB;
  72.                                 ans += aage;
  73.                         }
  74.                 }
  75.         }
  76.         cout << ans << endl;
  77.         return 0;
  78. }
  79.  
Success #stdin #stdout 0s 4548KB
comments (?)
stdin
copy 
5 2
1 10 100 3 2
stdout
copy 
22
https://ideone.com/gZSbmt
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!