Submission #1838497

---

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;
int DP(int I){
  vector<int> dp(N,INF);
  dp[0] = 0;
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++){
      if(i+j+1>n)break;
      int a = (I + i)%n;
      Min(dp[i+j+1],dp[i] + A[a]*(j+1) + x*j);
    }
  }
  return dp[n];
}

double calcTime(){
  static const clock_t start = clock();// スタート時間
  clock_t end = clock();     // 終了時間
  return (double)(end - start) / CLOCKS_PER_SEC;
}


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 ans = INF;

  for(int i=0;i<n&&calcTime()<1.7;i++) if(A[i] == I) Min(ans,DP(i));
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result