F7epXC - Online C++0x Compiler & Debugging Tool

/* Authors: Vu Hoang Bach from Phuoc Hoa Secondary School */

//#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")

#include <bits/stdc++.h>
#define ldb long double
//#define double ldb
#define db double
#define unomap unordered_map
#define unoset unordered_set
#define endl '\n'
#define str string
#define strstr stringstream
#define sz(a) (int)a.size()
#define ll long long
//#define int ll
#define pii pair <int, int>
#define pll pair <ll, ll>
#define Unique(a) a.resize(unique(all(a)) - a.begin())
#define ull unsigned ll
#define fir first
#define sec second
#define idc cin.ignore()
#define lb lower_bound
#define ub upper_bound
#define all(s) s.begin(), s.end()
#define rev reverse
#define sigma ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define skibidi int main
#define rizz signed main
#define gcd __gcd
#define found(a, mp) mp.find(a) != mp.end()
#define pushb push_back
#define popb pop_back
#define pushf push_front
#define popf pop_front
#define mul2x(a, x) a << x
#define div2x(a, x) a >> x
#define lcm(a, b) a / __gcd(a, b) * b
#define log_base(x, base) log(x) / log(base)
#define debug clog << "No errors!"; exit(0);
#define forw(i, a, b) for (int i = a; i <= b; ++i)
#define forw2(i, a, b) for (ll i = a; i <= b; ++i)
#define fors(i, a, b) for (int i = a; i >= b; --i)
#define fors2(i, a, b) for (ll i = a; i >= b; --i)
#define pqueue priority_queue
#define sqrt sqrtl
#define name "BUSROUTE"
#define want_digit(x) cout << fixed << setprecision(x);
#define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
using namespace std;
const int MOD = 1e9 + 7; // 998244353
const int inf = 1e9;
const ll INF = 1e18;
const int N = 1e2;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(const ll &L, const ll &R)
{
    return uniform_int_distribution<ll> (L, R) (rng);
}

template <class X, class Y>
bool minimize(X &x, const Y &y)
{
    return x > y ? x = y, true : false;
}

int n, k;
ll ans = INF, r[N + 5];

int prev(int x)
{
    if (!x) return k - 1;
    return x - 1;
}

int next(int x)
{
    if (x + 1 == k) return 0;
    return x + 1;
}

void recur(int pos, int cnt, vector <int> open)
{
    if (cnt == k)
    {
        ll sum = 0;
        int pos = lb(all(open), 1) - open.begin(), pos1;
        pos1 = prev(pos);
        forw (i, 1, n)
        {
            if (open[pos] < i)
            {
                pos1 = pos;
                pos = next(pos);
            }

            sum += r[i] * min(abs(open[pos] - i), abs(i - open[pos1]));
        }

        minimize(ans, sum);
        return;
    }

    if (pos > n || n - pos + 1 < k - cnt) return;

    recur(pos + 1, cnt, open);
    open.pushb(pos);
    recur(pos + 1, cnt + 1, open);
}

void cook()
{
    cin >> n >> k;
    forw (i, 1, n) cin >> r[i];

    vector <int> tmp;
    recur(1, 0, tmp);
    cout << ans << endl;
}

skibidi()
//rizz()
{
    srand(time(NULL));
    sigma;
    if (fopen(name".INP", "r"))
    {
        freopen(name".INP", "r", stdin);
        freopen(name".OUT", "w", stdout);
    }
    int numTest = 1;
//    cin >> numTest;
    while (numTest--)
    {
        cook();
    }
    return 0;
}