Submission #47281611

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)

using ld = long double;
const ld DELTA = 0.9, WORSE = numeric_limits<int>::min();

// stored DELTA ^ p
ld pow_d[5005];

// 1 + DELTA + .. DELTA ^ K
ld sum_k(int K) {
    return 1 * (1 - pow_d[K]) / (1 - DELTA);
}

// 1200 / sqrt(K)
ld off_term(int K) {
    if(K == 0)
        return 0;
    ld T = 1200;
    T /= sqrtl(K);
    return T;
}

void solve() {
    int n;
    cin >> n;
    vector<int>a(n);
    for(auto &i: a)
        cin >> i;

    vector<vector<ld>>dp(n + 1, vector<ld>(n + 1, WORSE));
    dp[0][0] = 0;

    for(int i = 1; i <= n; i++) {
        ld can_pick = a[i - 1];
        for(int picked = 1; picked <= n; picked++)
            dp[i][picked] = dp[i - 1][picked];
        for(int picked = 1; picked <= n; picked++) {
            ld best = dp[i - 1][picked - 1];
            if(best == WORSE) 
                continue;  
            /*
            let prev ans be Q
            if we want to add current performance to Q
            Q = Q - 1200 / root(picked - 1)
            Q = Q * (1 + DELTA + ... DELTA ^ (picked - 1))
            Q = Q * DELTA
            Q = Q + perf
            Q = Q / (1 + DELTA + .... DELTA ^ (picked))
            Q = Q - 1200 / root(picked)
            */
            best += off_term(picked - 1);
            best *= sum_k(picked - 1);
            best *= DELTA;
            best += can_pick;
            best /= sum_k(picked);
            best -= off_term(picked);
            dp[i][picked] = max(dp[i][picked], best);
        }
    }

    cout << setprecision(10) << *max_element(begin(dp[n]), end(dp[n])) << '\n';
    
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);
    pow_d[0] = 1;
    for(int i = 1; i <= 5002; i++) {
        pow_d[i] = (pow_d[i - 1] * DELTA);
    }
    int T = 1;
    while(T--) solve();
}

Submission Info

Judge Result