Submission #970920

#	Time	Username	Problem	Language	Result	Execution time	Memory
970920		vladilius	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	219 ms	524288 KiB

prison

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int inf = 1e9;
const ll infll = 1e18;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#define f first
#define s second

pii min(pii x, pii y){
    if (x.f == y.f){
        return {x.f, min(x.s, y.s)};
    }
    if (x.f > y.f) return y;
    return x;
}

ll min(ll x, ll y){
    if (x < y) return x;
    return y;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int n, d, t; cin>>n>>d>>t;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++){
        cin>>a[i];
    }
    
    vector<vector<int>> h(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n; i++){
        priority_queue<int, vector<int>, greater<int>> pq;
        int tt = 0, cnt = 0;
        for (int j = i; j <= n; j++){
            pq.push(a[j] - tt);
            int m = pq.top() + tt;
            cnt += (m <= t);
            h[i][j] = cnt;
            tt++;
        }
    }

    auto solve = [&](ld m){
        vector<vector<ld>> dp(n + 1, vector<ld>(2));
        vector<vector<int>> l(n + 1, vector<int>(2)), cnt(n + 1, vector<int>(2));

        dp[1][0] = infll;
        dp[1][1] = h[1][1];
        cnt[1][1] = 0;
        l[1][1] = 1;
        
        for (int i = 2; i <= n; i++){
            ld v1 = infll, v2 = infll;
            if (l[i - 1][0]) v1 = dp[l[i - 1][0]][1] + h[l[i - 1][0]][i] - h[l[i - 1][0]][l[i - 1][0]];
            if (l[i - 1][1]) v2 = dp[l[i - 1][1]][1] + h[l[i - 1][1]][i] - h[l[i - 1][1]][l[i - 1][1]];
            if (v1 < v2){
                dp[i][0] = v1;
                l[i][0] = l[i - 1][0];
                cnt[i][0] = cnt[i - 1][0];
            }
            else {
                dp[i][0] = v2;
                l[i][0] = l[i - 1][1];
                cnt[i][0] = cnt[i - 1][1];
            }
            
            v1 = dp[i - 1][0] + h[i][i] + m;
            v2 = dp[i - 1][1] + h[i][i] + m;
            if (v1 < v2){
                dp[i][1] = v1;
                l[i][1] = i;
                cnt[i][1] = cnt[i - 1][0] + 1;
            }
            else {
                dp[i][1] = v2;
                l[i][1] = i;
                cnt[i][1] = cnt[i - 1][1] + 1;
            }
        }
        
        /*
        for (int i = 1; i <= n; i++){
            cout<<dp[i][0]<<" "<<cnt[i][0]<<"\n";
        }
        cout<<"\n";
        for (int i = 1; i <= n; i++){
            cout<<dp[i][1]<<" "<<cnt[i][1]<<"\n";
        }
         */

        return min({dp[n][0], cnt[n][0]}, {dp[n][1], cnt[n][1]});
    };
    

    ld l = 0, r = inf;
    int tt = 1000;
    while (tt--){
        ld m = (l + r) / 2;
        auto [v, k] = solve(m);
        if (k > d){
            l = m;
        }
        else {
            r = m;
        }
    }
    
    auto [v1, k1] = solve(l);
    auto [v2, k2] = solve(r);
    // cout<<fixed<<setprecision(20)<<l<<" "<<v1<<" "<<k1<<"\n";
    // cout<<fixed<<setprecision(20)<<r<<" "<<v2<<" "<<k2<<"\n";

    ld out = n + 1;
    if (k1 <= d) out = min(out, v1 - k1 * l);
    if (k2 <= d) out = min(out, v2 - k2 * r);
    cout<<out<<"\n";
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 10
• Subtask 3: 0 / 20
• Subtask 4: 0 / 10
• Subtask 5: 0 / 25
• Subtask 6: 0 / 20