Submission #2559931

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <utility>
#include <climits>
using namespace std;

typedef long long ll;
const ll INF = LLONG_MAX;
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)

const ll siz = 200;
ll n, x, a[4002], cnt[2002]{}, xmax = 0, bucket[siz];

void init() {
    fill(bucket, bucket + siz, INF);
    REP(i, n * 2) { bucket[i / siz] = min(bucket[i / siz], a[i]); }
}
//[l,r)
ll rmq(ll l, ll r) {
    ll res = INF;
    REP(i, siz) {
        if ((i + 1) * siz < l || i * siz >= r) continue;
        if (i * siz >= l && (i + 1) * siz < r) {
            res = min(res, bucket[i]);
        } else {
            FOR(j, max(l, i * siz), min(r, (i + 1) * siz)) {
                res = min(res, a[j]);
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> x;
    REP(i, n) {
        cin >> a[i];
        a[i + n] = a[i];  // n->1のループをしやすくする
    }
    init();
    ll ans = INF;
    REP(t, n) {
        ll asum = 0;
        FOR(i, n, n * 2) { asum += rmq(i - t, i + 1); }
        ans = min(ans, asum + x * t);
    }
    cout << ans << endl;

    return 0;
}

Submission Info

Judge Result