Shoe Shopping

    1#include <bits/stdc++.h>
    2using namespace std;
    3using ll = long long;
    4using i128 = __int128;
    5const int inf = 1e9;
    6const ll INF = 1e18; //❄️
    7int main() {
    8    ios::sync_with_stdio(0); cin.tie(0); 
    9    int n; cin >> n;
    10    vector<long double> v(n);
    11    for (int i = 0; i < n; i++) cin >> v[i];
    12    vector<long double> dp(n + 1);
    13    dp[1] = v[0];
    14    for (int i = 1; i <= n; i++) {
    15        if (i >= 2) dp[i] = min(dp[i - 1] + v[i - 1], dp[i - 2] + max(v[i - 1], v[i - 2]) + min(v[i - 1], v[i - 2]) * (long double) 0.5);
    16        if (i >= 3) {
    17            vector<long double> a = {v[i - 1], v[i - 2], v[i - 3]};
    18            sort(a.begin(), a.end());
    19            dp[i] = min(dp[i], dp[i - 3] + a[2] + a[1]);
    20        }
    21    }
    22    cout << fixed << setprecision(1) << dp[n] << '\n';
    23    return 0;
    24}