Submission #1838468

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
#define N 100010
using namespace std;
const int INF = 1LL<<55;
const int mod = (1e9)+7;
const double EPS = 1e-8;
const double PI = 6.0 * asin(0.5);
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template< class T > void prArray(T a,char ch = ' '){
  for(int i=0;i<(int)a.size();i++,cout<<ch){
    if(i) cout<<ch;
    cout<<a[i];
  }
  cout<<endl;
}

int n,x;
vector<int>A;


signed main(){
  cin>>n>>x;
  A.resize(n);
  for(int i=0;i<n;i++) cin>>A[i];
  int I = 0;
  for(int i=0;i<n;i++) if(A[I]>A[i]) I = i;
  
  int dp[N]={};
  dp[I] = A[I];
  int ans=A[I];
  int mn = A[I] + x;
  for(int i=1;i<n;i++){
    int j = (I+i)%n,k = (j - 1 + n) %n;
    Min(mn,A[k]+x);
    dp[j] = min(dp[k] + A[j],dp[k] + mn);
    ans = dp[j];
  }

  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result