Submission #3780790

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll << 50;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  ll n, x; cin >> n >> x;
  vll a(n);
  REP(i, n) {
    cin >> a[i];
  }

  vvll dp(n);
  REP(i, n) {
    dp[i].resize(n);
    dp[i][0] = a[i];
  }

  vvll c(n);
  REP(i, n) {
    c[i].resize(n);
    c[i][0] = a[i];
  }

  REP(i, n) {
    FOR(j, 1, n) {
      dp[i][j] = min(dp[i][j-1], a[(i - j + n) % n] + j * x);
      if(dp[i][j-1] <= a[(i-j+n) % n] + j * x) {
        c[i][j] = c[i][j-1];
      } else {
        c[i][j] = a[(i-j+n) % n];
      }
    }
  }

  // REP(i, n) {
  //   printv(dp[i]);
  // }

  ll ans = LINF;
  REP(i, n) {
    ll su = 0;
    REP(j, n) {
      su += c[j][i];
    }
    ans = min(ans, su + x * i);
  }
  cout << ans << endl;
  
}

Submission Info

Judge Result